Back to Search
Start Over
Edge Guards in Straight Walkable Polygons.
- Source :
-
International Journal of Computational Geometry & Applications . Feb1999, Vol. 9 Issue 1, p63. 17p. - Publication Year :
- 1999
-
Abstract
- We study the art gallery problem restricted to edge guards and straight walkable polygons. An edge guard is the guard that patrols individual edges of the polygon. A simple polygon P is called straight walkable if there are two vertices s and t in P and we can move two points montonically on two polygonal chains of P from s to t, one clockwise and the other counterclockwise, such that two points are always mutually visible. For instance, monotone polygons and spiral polygons are straight walkable. We show that └(n+2)/5┘ edge guards are always sufficient to watch and n-vertex gallery of this type. Furthermore, we also show that if the given polygon is straight walkable and rectilinear, then └(n+3)/6┘ edge guards are sufficient. Both of our upper bounds match the known lower bounds. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 02181959
- Volume :
- 9
- Issue :
- 1
- Database :
- Academic Search Index
- Journal :
- International Journal of Computational Geometry & Applications
- Publication Type :
- Academic Journal
- Accession number :
- 10236292
- Full Text :
- https://doi.org/10.1142/S0218195999000066