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

ABSTRACT

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∈S b 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 R^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).

REFERENCES

• 1: Noga Alon , Michael Krivelevich , Benny Sudakov, Coloring graphs with sparse neighborhoods, Journal of Combinatorial Theory Series B, v.77 n.1, p.73-82, Sept. 1999 [doi>10.1006/jctb.1999.1910]
• 2: N. Alon and J. H. Spencer. The probabilistic method. Wiley Inter-Science, 2nd edition, 2000.
• 3: C. Berge. Hypergraphs. North Holland, Amsterdam, 1989.
• 4: Bernard Chazelle, The discrepancy method: randomness and complexity, Cambridge University Press, New York, NY, 2000
• 5: K. L. Clarkson , P. W. Shor, Applications of random sampling in computational geometry, II, Discrete & Computational Geometry, v.4 n.5, p.387-421, 1989 [doi>10.1007/BF02187740]
• 6: Mark de Berg , Marc van Kreveld , Mark Overmars , Otfried Schwarzkopf, Computational geometry: algorithms and applications, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 7: Alon Efrat, The complexity of the union of (&agr;, &bgr;)-covered objects, Proceedings of the fifteenth annual symposium on Computational geometry, p.134-142, June 13-16, 1999, Miami Beach, Florida, United States [doi>10.1145/304893.304958]
• 8: A. Efrat and M. Sharir. On the complexity of the union of fat convex objects in the plane. Discrete Comput. Geom., 23:171--189, 2000.
• 9: Jeff Erickson, Nice point sets can have nasty Delaunay triangulations, Proceedings of the seventeenth annual symposium on Computational geometry, p.96-105, June 2001, Medford, Massachusetts, United States [doi>10.1145/378583.378636]
• 10: Guy Even , Zvi Lotker , Dana Ron , Shakhar Smorodinsky, Conflict-Free Colorings of Simple Geometric Regions with Applications to Frequency Assignment in Cellular Networks, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.691-700, November 16-19, 2002
• 11: S. Har-Peled and S. Smorodinsky. On conflict-free coloring of points and simple regions in the plane. http://www.uiuc.edu/ sariel/research/ papers/02/coloring http://www.uiuc.edu/ gen%sariel/research/papers/02/\linebreakcoloring, 2003.
• 12: D. Haussler and E. Welzl. e-nets and simplex range queries. Discrete Comput. Geom., 2:127--151, 1987.
• 13: Klara Kedem , Ron Livne , János Pach , Micha Sharir, On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles, Discrete & Computational Geometry, v.1 n.1, p.59-71, 1986 [doi>10.1007/BF02187683]
• 14: J. Matouaek. Geometric Discrepancy. Springer, 1999.
• 15: J. Pach and G. Tath. Conflict free colorings. Discrete Comput. Geom., 2003. to appear (The Goodman-Pollack festschrift.).
• 16: Micha Sharir , Pankaj K. Agarwal, Davenport-Schinzel sequences and their geometric applications, Cambridge University Press, New York, NY, 1996
• 17: S. Smorodinsky. Combinatorial problems in computational geometry. Ph.D dissertation, Tel-Aviv University, in preparation, 2003.
• 18: D. B. West. Intorudction to Graph Theory. Prentice Hall, 2ed edition, 2001.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling

General Terms:
Algorithms, Theory

Keywords:
cellular network, coloring, frequency assignment