EDGE GUARDS IN STRAIGHT WALKABLE POLYGONS
Xuehou Tan · International Journal of Computational Geometry & Applications · 1999
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.