File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: A generalized fortress problem using k-consecutive vertex guards

TitleA generalized fortress problem using k-consecutive vertex guards
Authors
KeywordsComputational Geometry
Consecutive Vertex Guard
Fortress Problem
Issue Date2001
PublisherBirkhaeuser Verlag AG. The Journal's web site is located at http://link.springer.de/link/service/journals/00022/index.htm
Citation
Journal Of Geometry, 2001, v. 72 n. 1-2, p. 188-198 How to Cite?
AbstractThe fortress problem was posed independently by Joseph Malkelvitch and Derick Wood to determine the number of guards sufficient to cover the exterior of an n-vertex polygon. O'Rourke and Wood showed that [n/2] vertex guards are sometimes necessary and always sufficient. Yiu and Choi considered a variation of the problem by allowing each guard to patrol an edge (called an edge guard) of the polygon and obtained a tight bound of [n/3] edge guards for general polygons. In this paper, we unify and generalize both results by considering the number of k-consecutive vertex guards that are required to solve the fortress problem. A tight bound of [n/(k+1)] is obtained. © Birkhäuser Verlag, Basel, 2001.
Persistent Identifierhttp://hdl.handle.net/10722/152314
ISSN
2023 Impact Factor: 0.7
2023 SCImago Journal Rankings: 0.324
References

 

DC FieldValueLanguage
dc.contributor.authorYiu, SMen_US
dc.date.accessioned2012-06-26T06:37:07Z-
dc.date.available2012-06-26T06:37:07Z-
dc.date.issued2001en_US
dc.identifier.citationJournal Of Geometry, 2001, v. 72 n. 1-2, p. 188-198en_US
dc.identifier.issn0047-2468en_US
dc.identifier.urihttp://hdl.handle.net/10722/152314-
dc.description.abstractThe fortress problem was posed independently by Joseph Malkelvitch and Derick Wood to determine the number of guards sufficient to cover the exterior of an n-vertex polygon. O'Rourke and Wood showed that [n/2] vertex guards are sometimes necessary and always sufficient. Yiu and Choi considered a variation of the problem by allowing each guard to patrol an edge (called an edge guard) of the polygon and obtained a tight bound of [n/3] edge guards for general polygons. In this paper, we unify and generalize both results by considering the number of k-consecutive vertex guards that are required to solve the fortress problem. A tight bound of [n/(k+1)] is obtained. © Birkhäuser Verlag, Basel, 2001.en_US
dc.languageengen_US
dc.publisherBirkhaeuser Verlag AG. The Journal's web site is located at http://link.springer.de/link/service/journals/00022/index.htmen_US
dc.relation.ispartofJournal of Geometryen_US
dc.subjectComputational Geometryen_US
dc.subjectConsecutive Vertex Guarden_US
dc.subjectFortress Problemen_US
dc.titleA generalized fortress problem using k-consecutive vertex guardsen_US
dc.typeArticleen_US
dc.identifier.emailYiu, SM:smyiu@cs.hku.hken_US
dc.identifier.authorityYiu, SM=rp00207en_US
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.scopuseid_2-s2.0-10044247598en_US
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-10044247598&selection=ref&src=s&origin=recordpageen_US
dc.identifier.volume72en_US
dc.identifier.issue1-2en_US
dc.identifier.spage188en_US
dc.identifier.epage198en_US
dc.publisher.placeSwitzerlanden_US
dc.identifier.scopusauthoridYiu, SM=7003282240en_US
dc.identifier.issnl0047-2468-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats