# Item

ITEM ACTIONSEXPORT

Released

Conference Paper

#### Conflict-Free Colorings of Rectangle Ranges

##### MPS-Authors

##### Locator

There are no locators available

##### Fulltext (public)

There are no public fulltexts available

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

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: http://hdl.handle.net/11858/00-001M-0000-000F-2266-5

##### Abstract

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.