Fully-Dynamic and Kinetic Conflict-Free Coloring of Intervals with Respect to Points

作     者：Mark de Berg Tim Leijsen Aleksandar Markovic André van Renssen Marcel Roeloffzen Gerhard Woeginger 

作者机构：Eindhoven University of Technology 5600 MB Eindhoven the Netherlands University of Sydney NSW 2006 Australia Eindhoven University of Technology 5600 MB Eindhoven The Netherlands RWTH Aachen University 52062 Aachen Germany 

出 版 物：《International Journal of Computational Geometry & Applications》 

年 卷 期：2019年第29卷第1期

页      面：49-72页

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主　　题：Conflict-free coloring dynamic data structures kinetic data structures 

摘      要：We introduce the fully-dynamic conflict-free coloring problem for a set S of intervals in ℝ 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 Ω ( log n / log log n ) , and that any strategy using O ( 1 / 𝜀 ) colors needs Ω ( 𝜀 n 𝜀 ) 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 / 𝜀 ) colors at the cost of O ( n 𝜀 / 𝜀 ) 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.