Fully-Dynamic and Kinetic Conflict-Free Coloring of Intervals with Respect to Points

Authors Mark de Berg, Tim Leijsen, Aleksandar Markovic, André van Renssen, Marcel Roeloffzen, Gerhard Woeginger



PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2017.26.pdf
  • Filesize: 0.56 MB
  • 13 pages

Document Identifiers

Author Details

Mark de Berg
Tim Leijsen
Aleksandar Markovic
André van Renssen
Marcel Roeloffzen
Gerhard Woeginger

Cite AsGet BibTex

Mark de Berg, Tim Leijsen, Aleksandar Markovic, André van Renssen, Marcel Roeloffzen, and Gerhard Woeginger. Fully-Dynamic and Kinetic Conflict-Free Coloring of Intervals with Respect to Points. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 26:1-26:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.ISAAC.2017.26

Abstract

We introduce the fully-dynamic conflict-free coloring problem for a set S of intervals in R^1 with respect to points, where the goal is to maintain a conflict-free coloring for S under insertions and deletions. A coloring is conflict-free if for each point p contained in some interval, p is contained in an interval whose color is not shared with any other interval containing p. We investigate trade-offs between the number of colors used and the number of intervals that are recolored upon insertion or deletion of an interval. Our results include: - a lower bound on the number of recolorings as a function of the number of colors, which implies that with O(1) recolorings per update the worst-case number of colors is Omega(log n/log log n), and that any strategy using O(1/epsilon) colors needs Omega(epsilon n^epsilon) recolorings; - a coloring strategy that uses O(log n) colors at the cost of O(log n) recolorings, and another strategy that uses O(1/epsilon) colors at the cost of O(n^epsilon/epsilon) recolorings; - stronger upper and lower bounds for special cases. We also consider the kinetic setting where the intervals move continuously (but there are no insertions or deletions); here we show how to maintain a coloring with only four colors at the cost of three recolorings per event and show this is tight.
Keywords
  • Conflict-free colorings
  • Dynamic data structures
  • Kinetic data structures

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. M.A. Abam, M.J. Rezaei Seraji, and M. Shadravan. Online conflict-free coloring of intervals. Scientia Iranica, 21(6):2138-2141, 2014. URL: http://scientiairanica.sharif.edu/article_3607.html.
  2. A. Bar-Noy, P. Cheilaris, S. Olonetsky, and S. Smorodinsky. Online conflict-free colouring for hypergraphs. Combinatorics, Probability & Computing, 19(4):493-516, 2010. URL: http://dx.doi.org/10.1017/S0963548309990587.
  3. A. Bar-Noy, P. Cheilaris, and S. Smorodinsky. Deterministic conflict-free coloring for intervals: From offline to online. ACM Trans. Algorithms, 4(4):44:1-44:18, 2008. URL: http://dx.doi.org/10.1145/1383369.1383375.
  4. Andreas Bärtschi and Fabrizio Grandoni. On conflict-free multi-coloring. In Frank Dehne, Jörg-Rüdiger Sack, and Ulrike Stege, editors, Algorithms and Data Structures - 14th International Symposium, WADS 2015, Victoria, BC, Canada, August 5-7, 2015. Proceedings, volume 9214 of Lecture Notes in Computer Science, pages 103-114. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-319-21840-3_9.
  5. M. de Berg, O. Cheong, M. van Kreveld, and M. Overmars. Computational Geometry: Algorithms and Applications. Springer-Verlag, 3rd ed. edition, 2008. Google Scholar
  6. M. de Berg, T. Leijsen, A. Markovic, A. van Renssen, M. Roeloffzen, and G. Woeginger. Dynamic and kinetic conflict-free coloring of intervals with respect to points. CoRR, 2016. URL: http://arxiv.org/abs/1701.03388.
  7. P. Cheilaris, L. Gargano, A.A. Rescigno, and S. Smorodinsky. Strong conflict-free coloring for intervals. Algorithmica, 70(4):732-749, 2014. URL: http://dx.doi.org/10.1007/s00453-014-9929-x.
  8. K. Chen. How to play a coloring game against a color-blind adversary. In Proc. 22nd ACM Symp. Comput. Geom., pages 44-51, 2006. URL: http://dx.doi.org/10.1145/1137856.1137865.
  9. T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein. Introduction to Algorithms. The MIT Press, 3rd edition, 2009. Google Scholar
  10. G. Even, Z. Lotker, D. Ron, and S. Smorodinsky. Conflict-free colorings of simple geometric regions with applications to frequency assignment in cellular networks. SIAM Journal on Computing, 33(1):94-136, 2003. URL: http://dx.doi.org/10.1137/S0097539702431840.
  11. A. Fiat, M. Levy, J. Matousek, E. Mossel, J. Pach, M. Sharir, S. Smorodinsky, U. Wagner, and E. Welzl. Online conflict-free coloring for intervals. In Proc. 16th ACM-SIAM Symp. Discr. Alg., pages 545-554, 2005. URL: http://dl.acm.org/citation.cfm?id=1070432.1070506.
  12. S. Har-Peled and S. Smorodinsky. Conflict-free coloring of points and simple regions in the plane. Discrete & Computational Geometry, 34(1):47-70, 2005. URL: http://dx.doi.org/10.1007/s00454-005-1162-6.
  13. E. Horev, R. Krakovski, and S. Smorodinsky. Conflict-free coloring made stronger. In Proc. 12th Scandinavian Workshop. Alg. Theory, pages 105-117, 2010. Google Scholar
  14. S. Smorodinsky. Combinatorial Problems in Computational Geometry. PhD thesis, Tel-Aviv University, 2003. Google Scholar
  15. S. Smorodinsky. Conflict-free coloring and its applications. In Geometry — Intuitive, Discrete, and Convex: A Tribute to László Fejes Tóth, pages 331-389. Springer Berlin Heidelberg, 2013. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail