File Download
There are no files associated with this item.
Supplementary
-
Citations:
- Scopus: 0
- Appears in Collections:
Article: A generalized fortress problem using k-consecutive vertex guards
| Title | A generalized fortress problem using k-consecutive vertex guards |
|---|---|
| Authors | |
| Keywords | Computational Geometry Consecutive Vertex Guard Fortress Problem |
| Issue Date | 2001 |
| Publisher | Birkhaeuser 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? |
| Abstract | The 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 Identifier | http://hdl.handle.net/10722/152314 |
| ISSN | 2020 SCImago Journal Rankings: 0.395 |
| References |
| DC Field | Value | Language |
|---|---|---|
| dc.contributor.author | Yiu, SM | en_US |
| dc.date.accessioned | 2012-06-26T06:37:07Z | - |
| dc.date.available | 2012-06-26T06:37:07Z | - |
| dc.date.issued | 2001 | en_US |
| dc.identifier.citation | Journal Of Geometry, 2001, v. 72 n. 1-2, p. 188-198 | en_US |
| dc.identifier.issn | 0047-2468 | en_US |
| dc.identifier.uri | http://hdl.handle.net/10722/152314 | - |
| dc.description.abstract | The 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.language | eng | en_US |
| dc.publisher | Birkhaeuser Verlag AG. The Journal's web site is located at http://link.springer.de/link/service/journals/00022/index.htm | en_US |
| dc.relation.ispartof | Journal of Geometry | en_US |
| dc.subject | Computational Geometry | en_US |
| dc.subject | Consecutive Vertex Guard | en_US |
| dc.subject | Fortress Problem | en_US |
| dc.title | A generalized fortress problem using k-consecutive vertex guards | en_US |
| dc.type | Article | en_US |
| dc.identifier.email | Yiu, SM:smyiu@cs.hku.hk | en_US |
| dc.identifier.authority | Yiu, SM=rp00207 | en_US |
| dc.description.nature | link_to_subscribed_fulltext | en_US |
| dc.identifier.scopus | eid_2-s2.0-10044247598 | en_US |
| dc.relation.references | http://www.scopus.com/mlt/select.url?eid=2-s2.0-10044247598&selection=ref&src=s&origin=recordpage | en_US |
| dc.identifier.volume | 72 | en_US |
| dc.identifier.issue | 1-2 | en_US |
| dc.identifier.spage | 188 | en_US |
| dc.identifier.epage | 198 | en_US |
| dc.publisher.place | Switzerland | en_US |
| dc.identifier.scopusauthorid | Yiu, SM=7003282240 | en_US |
| dc.identifier.issnl | 0047-2468 | - |