On the Chromatic Art Gallery Problem.
Sándor P. Fekete, Stephan Friedrichs, Michael Hemmer, Joseph B. M. Mitchell, Christiane Schmidt · 2014
For a polygonal region P with n vertices, a guard cover S is a set of points in P, such that any point in P can be seen from a point in S. In a colored guard cover, every element in a guard cover is assigned a color, such that no two guards with the same color have overlapping visibility regions. The Chromatic Art Gallery Prob-lem (CAGP) asks for the minimum number of colors for which a colored guard cover exists. We discuss the CAGP for the case of only two colors. We show that it is already NP-hard to decide whether two colors suffice for covering a polygon with holes, even when arbitrary guard positions are allowed. For sim-ple polygons with a discrete set of possible guard loca-tions, we give a polynomial-time algorithm for deciding whether a two-colorable guard set exists. This algo-rithm can be extended to optimize various additional objective functions for two-colorable guard sets, in par-ticular minimizing the guard number, minimizing the maximum area of a visibility region, and minimizing or maximizing the overlap between visibility regions. We also show results for a larger number of colors: comput-ing the minimum number of colors in simple polygons with arbitrary guard positions is NP-hard for Θ(n) col-ors, but allows an O(log(OPT)) approximation for the number of colors. 1