Almost Tight Bounds for Conflict-Free Chromatic Guarding of Orthogonal Galleries

preprint2014arXivOpen access

Abstract

We address recently proposed chromatic versions of the classic Art Gallery Problem. Assume a simple polygon PP is guarded by a finite set of point guards and each guard is assigned one of tt colors. Such a chromatic guarding is said to be conflict-free if each point p∈Pp\in P sees at least one guard with a unique color among all guards visible from pp. The goal is to establish bounds on the function χcf(n)χ_{cf}(n) of the number of colors sufficient to guarantee the existence of a conflict-free chromatic guarding for any nn-vertex polygon. Bärtschi and Suri showed χcf(n)∈O(log⁡n)χ_{cf}(n)\in 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 pp and qq in an orthogonal polygon are r-visible to each other if the rectangle spanned by the points is contained in PP. For this model we show χcf(n)∈O(log⁡log⁡n)χ_{cf}(n)\in O(\log\log n) and χcf(n)∈Ω(log⁡log⁡n/log⁡log⁡log⁡n)χ_{cf}(n)\in Ω(\log\log n /\log\log\log 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)Θ(\log n)-bound. Our results can be interpreted as coloring results for special geometric hypergraphs.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.