Abstract
A conflict-free coloring for a given set of disks is a coloring of the disks such that for any point p on the plane there is a disk among the disks covering p having a color different from that of the rest of the disks that covers p. In the dynamic offline setting, a sequence of disks is given, we have to color the disks one-by-one according to the order of the sequence and maintain the conflict-free property at any time for the disks that are colored. This paper focuses on unit disks, i.e., disks with radius one. We give an algorithm that colors a sequence of n unit disks in the dynamic offline setting using O(logn) colors. The algorithm is asymptotically optimal because Ω(logn) colors is necessary to color some set of n unit disks for any value of n [9].
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Ajwani, D., Elbassioni, K.M., Govindarajan, S., Ray, S.: Conflict-free coloring for rectangle ranges using O(n .382) colors. In: The 19th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 181–187 (2007)
Alon, N., Smorodinsky, S.: Conflict-free colorings of shallow discs. In: The 22nd ACM Symposium on Computational Geometry (SoCG), pp. 41–43 (2006)
Bar-Noy, A., Cheilaris, P., Olonetsky, S., Smorodinsky, S.: Online conflict-free colorings for hypergraphs. In: Arge, L., Cachin, C., Jurdziński, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol. 4596, pp. 219–230. Springer, Heidelberg (2007)
Bar-Noy, A., Cheilaris, P., Smorodinsky, S.: Conflict-free coloring for intervals: from offline to online. In: The 18th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA), pp. 128–137 (2006)
Chen, K.: How to play a coloring game against a color-blind adversary. In: The 22nd ACM Symposium on Computational Geometry (SoCG), pp. 44–51 (2006)
Chen, K., Fiat, A., Kaplan, H., Levy, M., Matousek, J., Mossel, E., Pach, J., Sharir, M., Smorodinsky, S., Wagner, U., Welzl, E.: Online conflict-free coloring for intervals. SIAM J. Comput. 36(5), 1342–1359 (2007)
Chen, K., Kaplan, H., Sharir, M.: Online conflict-free coloring for halfplanes, congruent disks, and axis-parallel rectangles. ACM Transactions on Algorithms (in press)
Elbassioni, K.M., Mustafa, N.H.: Conflict-free colorings of rectangles ranges. In: Durand, B., Thomas, W. (eds.) STACS 2006. LNCS, vol. 3884, pp. 254–263. Springer, Heidelberg (2006)
Even, G., Lotker, Z., Ron, D., Smorodinsky, S.: Conflict-free colorings of simple geometric regions with applications to frequency assignment in cellular networks. SIAM J. Comput. 33(1), 94–136 (2003)
Har-Peled, S., Smorodinsky, S.: Conflict-free coloring of points and simple regions in the plane. Discrete & Computational Geometry 34(1), 47–70 (2005)
Hochbaum, D.S.: Efficient bounds for the stable set, vertex cover and set packing problems. Discrete Applied Mathematics 6(3), 243–254 (1983)
Pach, J., Tóth, G.: Conflict-free colorings. In: Aronov, B., Basu, S., Pach, J., Sharir, M. (eds.) Discrete and Computational Geometry – The Goodman-Pollack Festschrift. Springer, Heidelberg (2003)
Smorodinsky, S.: Combinatorial Problems in Computational Geometry. PhD thesis, Tel-Aviv University (2003)
Smorodinsky, S.: On the chromatic number of some geometric hypergraphs. In: The 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 316–323 (2006)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Chan, J.WT., Chin, F.Y.L., Hong, X., Ting, H.F. (2009). Dynamic Offline Conflict-Free Coloring for Unit Disks. In: Bampis, E., Skutella, M. (eds) Approximation and Online Algorithms. WAOA 2008. Lecture Notes in Computer Science, vol 5426. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-93980-1_19
Download citation
DOI: https://doi.org/10.1007/978-3-540-93980-1_19
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-93979-5
Online ISBN: 978-3-540-93980-1
eBook Packages: Computer ScienceComputer Science (R0)