An Efficient Algorithm for Mobile Guarded Guards in Simple Grids

摘要

A set of mobile guards in a grid is guarded if at any point on its patrol segment every guard can be seen by at least one other guard. Herein we discuss a class of polygon-bounded grids and simple grids for which we propose a quadratic time algorithm for solving the problem of finding the minimum set of mobile guarded guards (the MinMGG problem). Recall that the MinMGG problem is NP-hard even for grids every segment of which crosses at most three other segments. We also provide an O(n log n) time algorithm for the MinMGG problem in horizontally or vertically unobstructed grids. Finally, we investigate complete rectangular grids with obstacles. We show that if both the vertical and the horizontal sizes of the grid are larger than the number of obstacles k, k + 2 mobile guarded guards always suffice to cover the grid.