Dynamic conflict-free colorings in the plane

作     者：de Berg, Mark Markovic, Aleksandar 

作者机构：TU Eindhoven Eindhoven Netherlands 

出 版 物：《COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS》 (计算几何学)

年 卷 期：2019年第78卷

页      面：61-73页

核心收录：

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

基　　金：Netherlands' Organisation for Scientific Research (NWO) [024.002.003] 

主　　题：Conflict-free colorings Dynamic data structures 

摘      要：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(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 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 (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(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 (root 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. (C) 2018 Published by Elsevier B.V.