Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse




Conference Paper

Conflict-Free Colorings of Rectangle Ranges


Elbassioni,  Khaled
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Mustafa,  Nabil H.
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

There are no locators available
Fulltext (public)
There are no public fulltexts available
Supplementary Material (public)
There is no public supplementary material available

Elbassioni, K., & Mustafa, N. H. (2006). Conflict-Free Colorings of Rectangle Ranges. In STACS 2006, 23rd Annual Symposium on Theoretical Aspects of Computer Science (pp. 254-263). Berlin, Germany: Springer.

Cite as:
Given the range space , where P is a set of n points in and 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 is conflict-free. We study the following question: Given P, is it possible to add a small set of points Q such that can be colored with fewer colors than ? Our main result is the following: given P, and any , one can always add a set Q of points such that P ∪ Q can be conflict-free colored using 1 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.