Conflict-Free Colorings of Rectangles Ranges

Abstract

Given the range space ($P,\mathcal{R}$), where P is a set of n points in ℝ² and $\mathcal{R}$ is the family of subsets of P induced by all axis-parallel rectangles, the conflict-free coloring problem asks for a coloring of P with the minimum number of colors such that ($P,\mathcal{R}$) is conflict-free. We study the following question: Given P, is it possible to add a small set of points Q such that ($P \cup Q,\mathcal{R}$) can be colored with fewer colors than ($P,\mathcal{R}$)? Our main result is the following: given P, and any ε ≥ 0, one can always add a set Q of O(n ^1 − ε) points such that P ∪ Q can be conflict-free colored using $\tilde{O}(n^{\frac{3}{8}(1+\varepsilon)})$ colors. Moreover, the set Q and the conflict-free coloring can be computed in polynomial time, with high probability. Our result is obtained by introducing a general probabilistic re-coloring technique, which we call quasi-conflict-free coloring, and which may be of independent interest. A further application of this technique is also given.