Cooperative mobile guards in grids

摘要

A grid P is a connected union of vertical and horizontal segments. A mobile guard is a guard which is allowed to move along a grid segment, thus a point x is seen by a mobile guard g if either x is on the same segment as g or x is on a grid segment crossing g. A set of mobile guards is weakly cooperative if at any point on its patrol, every guard can be seen by at least one other guard. In this paper we discuss the classes of polygon-bounded grids and simple grids for which we propose a quadratic time algorithm for solving the problem of finding the minimum weakly cooperative guard set (MinWCMG). We also provide an O(nlogn) time algorithm for the MinWCMG problem in horizontally or vertically unobstructed grids. Next, we investigate complete rectangular grids with obstacles. We show that as long as both dimensions of a grid are larger than the number of obstacles k, k+2 weakly cooperative mobile guards always suffice to cover the grid. Finally, we prove that the MinWCMG problem is NP-hard even for grids in which every segment crosses at most three other segments. Consequently, the minimum k-periscope guard problem for 2D grids is NP-hard as well, and this answers the question posed by Gewali and Ntafos [L.P. Gewali, S. Ntafos, Covering grids and orthogonal polygons with periscope guards, Computational Geometry: Theory and Applications 2 (1993) 309–334].