On the chromatic art gallery problem

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 Problem (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 suće for covering a polygon with holes, even when arbitrary guard positions are allowed. For simple polygons with a discrete set of possible guard locations, we give a polynomial-time algorithm for deciding whether a two-colorable guard set exists. This algorithm can be extended to optimize various additional objective functions for two-colorable guard sets, in particular 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: computing the minimum number of colors in simple polygons with arbitrary guard positions is NP-hard for Θ(n) colors, but allows an O(log(OPT)) approximation for the number of colors.