2014/12/12 by Frank Hoffmann, Hoffmann, Frank, Klaus Kriegel +3
Computer Science · #Advanced Graph Theory Research #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Constraint Satisfaction and Optimization #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.1412.3984
openalex publication_date 2014/12/12 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28
We address recently proposed chromatic versions of the classic Art Gallery Problem. Assume a simple polygon P is guarded by a finite set of point guards and each guard is assigned one of t colors. Such a chromatic guarding is said to be conflict-free if each point p∈ P sees at least one guard with a unique color among all guards visible from p. The goal is to establish bounds on the function χcf(n) of the number of colors sufficient to guarantee the existence of a conflict-free chromatic guarding for any n-vertex polygon. Bärtschi and Suri showed χcf(n)∈ O(log n) (Algorithmica, 2014) for simple orthogonal polygons and the same bound applies to general simple polygons (Bärtschi et al., SoCG 2014). In this paper, we assume the r-visibility model instead of standard line visibility. Points p and q in an orthogonal polygon are r-visible to each other if the rectangle spanned by the points is contained in P. For this model we show χcf(n)∈ O(loglog n) and χcf(n)∈ Ω(loglog n /logloglog n). Most interestingly, we can show that the lower bound proof extends to guards with line visibility. To this end we introduce and utilize a novel discrete combinatorial structure called multicolor tableau. This is the first non-trivial lower bound for this problem setting.Furthermore, for the strong chromatic version of the problem, where all guards r-visible from a point must have distinct colors, we prove a Θ(log n)-bound. Our results can be interpreted as coloring results for special geometric hypergraphs.