Minimum Covers for Grids and Orthogonal Polygons by Periscope Guards

摘要

The problem of finding minimum guard covers in NP-hard for simple polygons andopen 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. Periscope visibility is the closest to standard visibility among various alternatives that have been proposed. We show that finding minimum periscope guard (as well as k-bend and s-guard) covers is NP-hard for 3-d grids. An O(n-cubed) algorithm for finding minimum periscope guard covers is presented in a simple grid with n segments. This result can be used to obtain minimum periscope guard covers for a class of simple orthogonal polygon in O(n-cubed). (JHD)