TY - JOUR

T1 - Fully-dynamic and kinetic conflict-free coloring of intervals with respect to points

AU - de Berg, Mark T.

AU - Leijsen, Tim

AU - Markovic, Aleksandar

AU - van Renssen, André

AU - Roeloffzen, Marcel

AU - Woeginger, Gerhard J.

PY - 2019/3/1

Y1 - 2019/3/1

N2 - 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 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 ω(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.

AB - 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 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 ω(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.

KW - Conflict-free coloring

KW - dynamic data structures

KW - kinetic data structures

UR - http://www.scopus.com/inward/record.url?scp=85071040944&partnerID=8YFLogxK

U2 - 10.1142/S021819591940003X

DO - 10.1142/S021819591940003X

M3 - Article

AN - SCOPUS:85071040944

SN - 0218-1959

VL - 29

SP - 49

EP - 72

JO - International Journal of Computational Geometry and Applications

JF - International Journal of Computational Geometry and Applications

IS - 1

ER -