Conflict-free colorings of shallow discs

ABSTRACT

We prove that any collection of n discs in which each one intersects at most k others, can be colored with at most O(log³k) 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.

REFERENCES

• 1: N. Alon and J. H. Spencer. The Probabilistic Method, 2nd edition. Wiley, 2000.
• 2: A. Bar-Noy, P. Hillaris and S. Smorodinsky. Conflict-Free coloring for intervals: from offline to online. submitted.
• 3: A. Bar-Noy, P. Hillaris and S. Smorodinsky. Randomized online conflict-free colorings for hypergraphs, manuscript 2006.
• 4: Ke Chen, How to play a coloring game against a color-blind adversary, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA [doi>10.1145/1137856.1137865]
• 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
• 6: K. Elbassioni and N. Mustafa, Conflict-Free colorings for rectangle ranges, In proc. the 23rd International Symposium on Theoretical Aspects of Computer Science (STACS 2006).
• 7: Guy Even , Zvi Lotker , Dana Ron , Shakhar Smorodinsky, Conflict-Free Colorings of Simple Geometric Regions with Applications to Frequency Assignment in Cellular Networks, SIAM Journal on Computing, v.33 n.1, p.94-136, 2004 [doi>10.1137/S0097539702431840]
• 8: Amos Fiat , Meital Levy , Jiří Matoušek , Elchanan Mossel , János Pach , Micha Sharir , Shakhar Smorodinsky , Uli Wagner , Emo Welzl, Online conflict-free coloring for intervals, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 9: Sariel Har-Peled , Shakhar Smorodinsky, Conflict-Free Coloring of Points and Simple Regions in the Plane, Discrete & Computational Geometry, v.34 n.1, p.47-70, July 2005 [doi>10.1007/s00454-005-1162-6]
• 10: H. Kaplan and M. Sharir, Online CF coloring for halfplanes, congruent disks, and axis-parallel rectangles, manuscript, 2004.
• 11: 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]
• 12: J. Pach and G. Tóth. Conflict free colorings. In Discrete and Computational Geometry, The Goodman-Pollack Festschrift. Springer Verlag, Heidelberg, 2003.
• 13: S. Smorodinsky, Combinatorial Problems in Computational Geometry, Ph.D Dissertation, School of Computer Science, Tel-Aviv University, 2003.
• 14: Shakhar Smorodinsky, On the chromatic number of some geometric hypergraphs, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.316-323, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109593]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Algorithms, Theory

Keywords:
combinatorics, conflict-free coloring, frequency-assignment, wireless