TY - JOUR
T1 - Dynamic conflict-free colorings in the plane
AU - de Berg, Mark
AU - Markovic, Aleksandar
PY - 2019/6/1
Y1 - 2019/6/1
N2 - We study dynamic conflict-free colorings in the plane, where the goal is to maintain a conflict-free coloring (CF-coloring for short) under insertions and deletions. • First we consider CF-colorings of a set S of unit squares with respect to points. Our method maintains a CF-coloring that uses O(logn) colors at any time, where n is the current number of squares in S, at the cost of only O(logn) recolorings per insertion or deletion of a square. We generalize the method to rectangles whose sides have lengths in the range [1,c], where c is a fixed constant. Here the number of colors used becomes O(log2n). The method also extends to arbitrary rectangles whose coordinates come from a fixed universe of size N, yielding O(log2Nlog2n) colors. The number of recolorings for both methods stays in O(logn).• We then present a general framework to maintain a CF-coloring under insertions for sets of objects that admit a unimax coloring with a small number of colors in the static case. As an application we show how to maintain a CF-coloring with O(log3n) colors for disks (or other objects with linear union complexity) with respect to points at the cost of O(logn) recolorings per insertion. We extend the framework to the fully-dynamic case when the static unimax coloring admits weak deletions. As an application we show how to maintain a CF-coloring with O(nlog2n) colors for points with respect to rectangles, at the cost of O(logn) recolorings per insertion and O(1) recolorings per deletion.These are the first results on fully-dynamic CF-colorings in the plane, and the first results for semi-dynamic CF-colorings for non-congruent objects.
AB - We study dynamic conflict-free colorings in the plane, where the goal is to maintain a conflict-free coloring (CF-coloring for short) under insertions and deletions. • First we consider CF-colorings of a set S of unit squares with respect to points. Our method maintains a CF-coloring that uses O(logn) colors at any time, where n is the current number of squares in S, at the cost of only O(logn) recolorings per insertion or deletion of a square. We generalize the method to rectangles whose sides have lengths in the range [1,c], where c is a fixed constant. Here the number of colors used becomes O(log2n). The method also extends to arbitrary rectangles whose coordinates come from a fixed universe of size N, yielding O(log2Nlog2n) colors. The number of recolorings for both methods stays in O(logn).• We then present a general framework to maintain a CF-coloring under insertions for sets of objects that admit a unimax coloring with a small number of colors in the static case. As an application we show how to maintain a CF-coloring with O(log3n) colors for disks (or other objects with linear union complexity) with respect to points at the cost of O(logn) recolorings per insertion. We extend the framework to the fully-dynamic case when the static unimax coloring admits weak deletions. As an application we show how to maintain a CF-coloring with O(nlog2n) colors for points with respect to rectangles, at the cost of O(logn) recolorings per insertion and O(1) recolorings per deletion.These are the first results on fully-dynamic CF-colorings in the plane, and the first results for semi-dynamic CF-colorings for non-congruent objects.
KW - Conflict-free colorings
KW - Dynamic data structures
UR - http://www.scopus.com/inward/record.url?scp=85055550688&partnerID=8YFLogxK
U2 - 10.1016/j.comgeo.2018.10.005
DO - 10.1016/j.comgeo.2018.10.005
M3 - Article
AN - SCOPUS:85055550688
VL - 78
SP - 61
EP - 73
JO - Computational Geometry
JF - Computational Geometry
SN - 0925-7721
ER -