Title: Fully-Dynamic and Kinetic Conflict-Free Coloring of Intervals with Respect to Points,
Abstract: We introduce the fully-dynamic conflict-free coloring problem for a set $S$
of intervals in $\mathbb{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/\varepsilon)$ colors needs $\Omega(\varepsilon n^{\varepsilon})$
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/\varepsilon)$ colors at the
cost of $O(n^{\varepsilon}/\varepsilon)$ 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.