Dynamic and kinetic conflict-free coloring of intervals with respect to points

M.T. de Berg, T. Leijsen, André M. van Renssen, M.J.M. Roeloffzen, A. Markovic, G. Woeginger

Research output: Contribution to journalArticleAcademic

65 Downloads (Pure)


We introduce the 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. 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 Ω(logn/loglogn) , and that any strategy using O(1/ε) colors needs Ω(εn ε ) recolorings;
- a coloring strategy that uses O(logn) colors at the cost of O(logn) recolorings, and another strategy that uses O(1/ε) colors at the cost of O(n ε /ε) 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.
Original languageEnglish
Article number1701.03388
Number of pages17
Issue number1701.03388
Publication statusPublished - 2017


  • Computational Geometry


Dive into the research topics of 'Dynamic and kinetic conflict-free coloring of intervals with respect to points'. Together they form a unique fingerprint.

Cite this