View article

In FOCS 2002, Even et al. showed that any set of n discs in the plane can be Conflict-Free colored with a total of at most O(logn) colors. That is, it can be colored with O(logn) colors such that for any (covered) point p there is some disc whose color is distinct from all other colors of discs containing p. They also showed that this bound is asymptotically tight. In this paper we prove the following stronger results:

(i) Any set of n discs in the plane can be colored with a total of at most O(k logn) colors such that (a) for any point p that is covered by at least k discs, there are at least k distinct discs each of which is colored by a color distinct from all other discs containing p and (b) for any point p covered by at most k discs, all discs covering p are colored distinctively. We call such a coloring a k-Strong Conflict-Free coloring. We extend this result to pseudo-discs and arbitrary regions with linear union-complexity …