Cooperative mobile guards in grids (Q876501)

Mobile guards in grids are studied here. Considering the classes of polygon-bounded grids, and simple grids [\textit{L. P. Gewali} and \textit{S. Ntafos}, Comput. Geom. 2, No. 6, 309--334 (1993; Zbl 0774.68058)], the authors propose a quadratic time algorithm for solving the problem of finding a minimum weakly cooperative guard set. This algorithm is based upon the property that horizontal and vertical grid segments may be covered independently, whereas the constructed guard set satisfies the condition of weak cooperation. Finally, complete rectangular grids with obstacles are investigated.