We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
Edge Guards in Straight Walkable Polygons.
- Authors
Tan, Xuehou; Asano, T.
- 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.
- Subjects
GEOMETRY; POLYGONS
- Publication
International Journal of Computational Geometry & Applications, 1999, Vol 9, Issue 1, p63
- ISSN
0218-1959
- Publication type
Article
- DOI
10.1142/S0218195999000066