Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

We present randomized algorithms for online conflict-free coloring (CF in short) of points in the plane, with respect to halfplanes, congruent disks, and nearly-equal axis-parallel rectangles. In all three cases, the coloring algorithms use O(log n) colors, with high probability.

We also present a deterministic algorithm for online CF coloring of points in the plane with respect to nearly-equal axis-parallel rectangles, using O(log³n) colors. This is the first efficient (i.e, using polylog(n) colors) deterministic online CF coloring algorithm for this problem.

REFERENCES

• 1: Deepak Ajwani , Khaled Elbassioni , Sathish Govindarajan , Saurabh Ray, Conflict-free coloring for rectangle ranges using O(n^.382) colors, Proceedings of the nineteenth annual ACM symposium on Parallel algorithms and architectures, June 09-11, 2007, San Diego, California, USA [doi>10.1145/1248377.1248406]
• 2: 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]
• 3: Bar-Noy, A., Cheilaris, P., Olonetsky, S., and Smorodinsky, S. 2007. Online conflict-free coloring for hypergraphs. In Proceedings of the 34th International Colloquiun on Automata, Languages and Programming (ICALP'07). ACM, New York, 219--230.
• 4: Amotz Bar-Noy , Panagiotis Cheilaris , Shakhar Smorodinsky, Conflict-free coloring for intervals: from offline to online, Proceedings of the eighteenth annual ACM symposium on Parallelism in algorithms and architectures, July 30-August 02, 2006, Cambridge, Massachusetts, USA [doi>10.1145/1148109.1148133]
• 5: Allan Borodin , Ran El-Yaniv, Online computation and competitive analysis, Cambridge University Press, New York, NY, 1998
• 6: 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]
• 7: Ke Chen , Amos Fiat , Haim Kaplan , Meital Levy , Jirˇi´ Matousˇek , Elchanan Mossel , Ja´nos Pach , Micha Sharir , Shakhar Smorodinsky , Uli Wagner , Emo Welzl, Online Conflict-Free Coloring for Intervals, SIAM Journal on Computing, v.36 n.5, p.1342-1359, December 2006 [doi>10.1137/S0097539704446682]
• 8: de Berg, M., van Kreveld, M., Overmars, M., and Schwarzkopf, O. 2000. Computat. Geom. Algo. Appl., 2nd ed. Springer-Verlag, Berlin, Germany.
• 9: 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]
• 10: 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]
• 11: Pach, J., and Tóth, G. 2003. Conflict-free colorings. In Discrete and Computational Geometry, The Goodman-Pollack Festschrift, B. Aronov, S. Basu, J. Pach, and M. Sharir, Eds. Springer-Verlag, Berlin, Germany, 665--671.
• 12: Smorodinsky, S. 2003. Combinatorial problems in computational geometry. PhD dissertation, School of Computer Science, Tel-Aviv University, Tel-Aviv, Israel.
• 13: Shakhar Smorodinsky, On The Chromatic Number of Geometric Hypergraphs, SIAM Journal on Discrete Mathematics, v.21 n.3, p.676-687, July 2007 [doi>10.1137/050642368]
• 14: Jean Vuillemin, A unifying look at data structures, Communications of the ACM, v.23 n.4, p.229-239, April 1980 [doi>10.1145/358841.358852]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

General Terms:
Algorithms

Keywords:
Conflict free coloring, coloring, online algorithms