On conflict-free coloring of points and simple regions in the plane

In this paper, we study coloring problems related to frequency assignment problems in cellular networks. In abstract setting, the problems are of the following two types: CF-coloring of regions: Given a finite family S of n regions of some fixed type (such as discs, pseudo-discs, axis-parallel rectangles, etc.), what is the minimum integer k, such that one can assign a color to each region of S, using a total of at most k colors, such that the resulting coloring has the following property: For each point p ∈ ∪_b∈Sb there is at least one region b ∈ S that contains p in its interior, whose color is unique among all regions in S that contain p in their interior (in this case we say that p is being 'served' by that color). We refer to such a coloring as a conflict-free coloring of S (CF-coloring in short). CF-coloring of a range space: Given a set P of n points in ℝ^d and a set R of ranges (for example, the set of all discs in the plane), what is the minimum integer k, such that one can color the points of P by k colors, so that for any r ∈ R, with P ∩ r ≠ θ, there is at least one point q ∈ P ∩ r that is assigned a unique color among all colors assigned to points of P ∩ r (in this case we say that r is 'served' by that color). We refer to such a coloring as a conflict-free coloring of (P, R) (CF-coloring in short).