ICS Theory Group

ICS 269, Spring 2006: Theory Seminar

May 19, 2006, in CS 243

Conflict-Free Coloring of Shallow Discs

Authored by: N. Alon and S. Smorodinsky

(to appear in Symp. on Computational Geometry, SoCG'06)

Presented by Jeremy Yu Meng


We prove that any collection of n discs in which each one intersects at most k others, can be colored with at most O(log3k) colors so that for each point p in the union of all discs there is at least one disc in the collection containing p whose color differs from that of all other members of the collection that contain p. This is motivated by a problem on frequency assignments in cellular networks, and improves the best previously known upper bound of O(log n) when k is much smaller than n.