Cooperative guards in art galleries
Volume 450 / 2007
Abstract
The art gallery problem was originally posed by Victor Klee in 1973 as the question of determining the minimum number of guards sufficient to see every point of the interior of an $n$-vertex simple polygon. The guard is assumed to be a stationary point which can see any other point that can be connected to it by a line segment within the art gallery. The first result is due to Chvátal (1975), who proved that $\lfloor{n}/{3}\rfloor$ guards are occasionally necessary and always sufficient to cover a polygon with $n$~vertices. Since then many different variations of this problem have arisen, and in this dissertation, we investigate the {\it cooperative guards problem} posed by Liaw, Huang and Lee in 1993. In general, two variants of the cooperation are distinguished: a guard set is said to be cooperative provided that for any guard, if something goes wrong with him, all the others can be informed (by using the line-of-sight communication only), and $k$-guarded if each guard is seen by at least $k$ of its colleagues. We present tight bounds for various classes of galleries (arbitrary, orthogonal, monotone, spiral, star-shaped, with holes) as well as we discuss the complexity of the problem of determining the minimum number of cooperative (resp. $k$-guarded) guards sufficient to cover an art gallery. Finally, we investigate the cooperative guards problem in fortresses and grids.
