Improved bounds for the conflict-free chromatic art gallery problem
Andreas Bärtschi, Subir Kumar Ghosh, Matúš Mihaľák, Thomas Tschager, Peter Widmayer · 2014
In chromatic variants of the art gallery problem, simple polygons are guarded with point guards that are assigned one of k colors each. We say these guards cover the polygon. Here we consider the conflict-free chromatic art gallery problem, first studied by Bärtschi and Suri (Algorithmica 2013): A covering of the polygon is conflict-free if each point of the polygon is seen by some guard whose color appears exactly once among the guards visible to that point. We are interested in the smallest number k(n) of colors that ensure such a covering for every n-vertex polygon.