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

ABSTRACT

We consider an online version of the conflict-free coloring of a set of points on the line, where each newly inserted point must be assigned a color upon insertion, and at all times the coloring has to be conflict-free, in the sense that in every interval I there is a color that appears exactly once in I. We present several deterministic and randomized algorithms for achieving this goal, and analyze their performance, that is, the maximum number of colors that they need to use, as a function of the number n of inserted points. We first show that a natural and simple (deterministic) approach may perform rather poorly, requiring Ω(√n) colors in the worst case. We then modify this approach, to obtain an efficient deterministic algorithm that uses a maximum of Θ(log² n) colors. Next, we present two randomized solutions. The first algorithm requires an expected number of at most O(log² n) colors, and produces a coloring which is valid with high probability, and the second one, which is a variant of our efficient deterministic algorithm, requires an expected number of at most O(log n log log n) colors but always produces a valid coloring. We also analyze the performance of the simplest proposed algorithm when the points are inserted in a random order, and present an incomplete analysis that indicates that, with high probability, it uses only O(log n) colors. Finally, we show that in the extension of this problem to two dimensions, where the relevant ranges are disks, n colors may be required in the worst case. The average-case behavior for disks, and cases involving other planar ranges, are still open.

REFERENCES

• 1: N. Alon and J. Spencer, The Probabilistic Method, J. Wiley and Sons, New York, NY, 1992.
• 2: K. B. Athreya and P. E. Ney, Branching Processes, Die Grundlehren der mathematischen Wissenschaften, Band 196, Springer-Verlag, New York, 1972.
• 3: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 4: Jitender S. Deogun , Ton Kloks , Dieter Kratsch , Haiko Müller, On Vertex Ranking for Permutations and Other Graphs, Proceedings of the 11th Annual Symposium on Theoretical Aspects of Computer Science, p.747-758, February 24-26, 1994
• 5: 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]
• 6: Sariel Har-Peled , Shakhar Smorodinsky, On conflict-free coloring of points and simple regions in the plane, Proceedings of the nineteenth annual symposium on Computational geometry, June 08-10, 2003, San Diego, California, USA [doi>10.1145/777792.777810]
• 7: S. Smorodinsky, Combinatorial Problems in Computational Geometry, Ph.D Dissertation, School of Computer Science, Tel-Aviv University, 2003.