Covering grids and orthogonal polygons with periscope guards

AbstractThe problem of finding minimum guard covers is NP-hard for simple polygons and open for simple orthogonal polygons. Alternative definitions of visibility have been considered for orthogonal polygons. In this paper we try to determine the complexity of finding guard covers in orthogonal polygons by considering periscope visibility. Under periscope visibility, two points in an orthogonal polygon are visible if there is an orthogonal path with at most one bend that connects them without intersecting the exterior of the polygon. We show that finding minimum periscope guard (as well as k-periscope and s-guard) covers is NP-hard for 3-d grids. We present an O(n3) algorithm for finding minimum periscope guard covers for simple grids and discuss how to extend the algorithm to obtain minimum k-periscope guard covers. We show that this algorithm can be applied to obtain minimum periscope guard covers for a class of simple orthogonal polygon in O(n3)