TY - GEN

T1 - Conflict-free colorings of rectangles ranges

AU - Elbassioni, Khaled

AU - Mustafa, Nabil H.

PY - 2006

Y1 - 2006

N2 - Given the range space (P, R), where P is a set of n points in IR 2 and 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, 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 ∪ Q, R) can be colored with fewer colors than (P, R)? Our main result is the following: given P, and any ε ≥ 0, one can always add a set Q of O(n1-ε) points such that P ∪ Q can be conflict-free colored using Õ(n3/8(1+ε))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 recoloring technique, which we call quasi-conflict-free coloring, and which may be of independent interest. A further application of this technique is also given.

AB - Given the range space (P, R), where P is a set of n points in IR 2 and 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, 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 ∪ Q, R) can be colored with fewer colors than (P, R)? Our main result is the following: given P, and any ε ≥ 0, one can always add a set Q of O(n1-ε) points such that P ∪ Q can be conflict-free colored using Õ(n3/8(1+ε))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 recoloring technique, which we call quasi-conflict-free coloring, and which may be of independent interest. A further application of this technique is also given.

UR - http://www.scopus.com/inward/record.url?scp=33745626102&partnerID=8YFLogxK

U2 - 10.1007/11672142_20

DO - 10.1007/11672142_20

M3 - Conference contribution

AN - SCOPUS:33745626102

SN - 3540323015

SN - 9783540323013

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 254

EP - 263

BT - STACS 2006

T2 - STACS 2006: 23rd Annual Symposium on Theoretical Aspects of Computer Science, Proceedings

Y2 - 23 February 2006 through 25 February 2006

ER -