de Berg, Mark ;
Leijsen, Tim ;
Markovic, Aleksandar ;
van Renssen, André ;
Roeloffzen, Marcel ;
Woeginger, Gerhard
FullyDynamic and Kinetic ConflictFree Coloring of Intervals with Respect to Points
Abstract
We introduce the fullydynamic conflictfree coloring problem for a set S of intervals in R^1 with respect to points, where the goal is to maintain a conflictfree coloring for S under insertions and deletions. A coloring is conflictfree 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 tradeoffs 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 worstcase number of colors is Omega(log n/log log n), and that any strategy using O(1/epsilon) colors needs Omega(epsilon n^epsilon) 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/epsilon) colors at the cost of O(n^epsilon/epsilon) 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.
BibTeX  Entry
@InProceedings{deberg_et_al:LIPIcs:2017:8268,
author = {Mark de Berg and Tim Leijsen and Aleksandar Markovic and Andr{\'e} van Renssen and Marcel Roeloffzen and Gerhard Woeginger},
title = {{FullyDynamic and Kinetic ConflictFree Coloring of Intervals with Respect to Points}},
booktitle = {28th International Symposium on Algorithms and Computation (ISAAC 2017)},
pages = {26:126: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/8268},
URN = {urn:nbn:de:0030drops82683},
doi = {10.4230/LIPIcs.ISAAC.2017.26},
annote = {Keywords: Conflictfree colorings, Dynamic data structures, Kinetic data structures}
}
2017
Keywords: 

Conflictfree colorings, Dynamic data structures, Kinetic data structures 
Seminar: 

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

Issue date: 

2017 
Date of publication: 

2017 