Edge Guards in Straight Walkable Polygons.

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]