2017/01/12 by de Berg, Mark, Leijsen, Tim, van Renssen, André +3
#Computational Geometry (cs.CG) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1701.03388
We introduce the fully-dynamic conflict-free coloring problem for a set S of intervals in ℝ1 with respect to points, where the goal is to maintain a conflict-free coloring forS 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 Ω(log n/loglog n), and that any strategy using O(1/ε) colors needs Ω(ε nε) 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/ε) 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.