## Abstract

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 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 Nlog 2 n) 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(log 3 n) 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(n − − √ log 2 n) 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.

- 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 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 Nlog 2 n) 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(log 3 n) 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(n − − √ log 2 n) 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.

Original language | English |
---|---|

Article number | 1709.10466 |

Journal | arXiv |

Issue number | 1709.10466 |

Publication status | Published - 2017 |

## Keywords

- Computational Geometry
- Dynamic data structures
- Conflict-free colorings