Title:  Conflict-Free Colorings of Rectangular Ranges 
Speaker: Khaled Elbassioni
MPI, Saarbrucken

Date: Tuesday,  May 23, 2006
Time 2-3PM
Venue: Room 3464 (Math-CS Conference Room) HKUST   

  
Abstract:
Given a set of N points P in the plane, we would 
like to color the points with the minimum number of colors, 
such that every axis-parallel rectangle containing a point 
of P, has a point of a unique color. Such a coloring is 
called a "conflict-free coloring", and is motivated by an 
application of frequency assignment in wireless networks.

It is known that O(\sqrt{N}) colors are enough, but open 
whether this can be reduced to polylog(n).
In this talk, we will consider the following question: 
Given P, is it possible to add a small set of points Q such 
that P+Q can be conflict-free colored with fewer colors than P?

The answer is yes: for any \epsilon>0, one can always add 
a set Q of  O(N^{1-\epsilon})  points such that P+Q can be 
conflict-free colored using O(N^{\frac{3}{8} (1+\eps)}) colors. 
This can be achieved through a general probabilistic 
re-coloring technique, which we call "quasi-conflict-free" coloring.

As a further application of this technique, we can show that 
a non-uniform grid of N points can be conflict-free colored 
with O(N^{3/8+\epsilon}) colors, for any \epsilon>0. 


This is joint work with Nabil H. Mustafa.