Abstract
We study dynamic conflictfree colorings in the plane, where the goal is to maintain a conflictfree coloring (CFcoloring for short) under insertions and deletions.
 First we consider CFcolorings of a set S of unit squares with respect to points. Our method maintains a CFcoloring that uses O(log n) colors at any time, where n is the current number of squares in S, at the cost of only O(log n) recolorings per insertion or deletion 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 used colors becomes O(log^2 n). The method also extends to arbitrary rectangles whose coordinates come from a fixed universe of size N, yielding O(log^2 N log^2 n) colors. The number of recolorings for both methods stays in O(log n).
 We then present a general framework to maintain a CFcoloring 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 CFcoloring with O(log^3 n) colors for disks (or other objects with linear union complexity) with respect to points at the cost of O(log n) recolorings per insertion. We extend the framework to the fullydynamic case when the static unimax coloring admits weak deletions. As an application we show how to maintain a CFcoloring with O(sqrt(n) log^2 n) colors for points with respect to rectangles, at the cost of O(log n) recolorings per insertion and O(1) recolorings per deletion.
These are the first results on fullydynamic CFcolorings in the plane, and the first results for semidynamic CFcolorings for noncongruent objects.
BibTeX  Entry
@InProceedings{deberg_et_al:LIPIcs:2017:8250,
author = {Mark de Berg and Aleksandar Markovic},
title = {{Dynamic ConflictFree Colorings in the Plane}},
booktitle = {28th International Symposium on Algorithms and Computation (ISAAC 2017)},
pages = {27:127:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770545},
ISSN = {18688969},
year = {2017},
volume = {92},
editor = {Yoshio Okamoto and Takeshi Tokuyama},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/8250},
URN = {urn:nbn:de:0030drops82504},
doi = {10.4230/LIPIcs.ISAAC.2017.27},
annote = {Keywords: Conflictfree colorings, Dynamic data structures}
}
Keywords: 

Conflictfree colorings, Dynamic data structures 
Collection: 

28th International Symposium on Algorithms and Computation (ISAAC 2017) 
Issue Date: 

2017 
Date of publication: 

07.12.2017 