Title: Coloring geometric range spaces 

Speaker: Stefan Langerman 
Université Libre de Bruxelles

Date: Monday  August 10, 2009
Time 11:30AM- 12:30PM
Venue: Room 3464, HKUST

Abstract: Title: Coloring geometric range spaces

We study several coloring problems for geometric range-spaces, 
partly motivated by a sensor network problem. Given a set of 
points in R2 or R3, we want to color them such that every region 
of a certain family (e.g., every disk containing at least a 
certain number of points) contains points of many different 
colors. For most region families, for a fixed k using k colors, 
it is not always possible to ensure that every region containing 
k points has k colors present. Thus, we consider two types of 
relaxations: either we allow the total number of colors to 
increase to c(k), or we require that the number of points 
in each region increases to p(k).
Symmetrically, given a finite set of regions in R2 or R3, 
we want to color them such that every point covered by a 
sufficiently large number of regions is contained in 
regions of k different colors. This requires the number 
of covering regions or the number of allowed colors to
 be greater than k.

Our goal is to bound the two functions c(k) and p(k) 
for several types of region families, such as halfplanes, 
halfspaces, translates of polygons, disks and pseudo-disks. 
We improve and generalize previous results of Pach, Tardos 
and Tóth on decompositions of space coverings.

Joint work with Greg Aloupis, Jean Cardinal, 
Sébastien Collette, Stefan Langerman, David Orden, 
Pedro Ramos, and Shakhar Smorodinski.