2026-08-10T12:14:57Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8268 2024-03-06T10:41:48Z ddc:004 open_access

Fully-Dynamic and Kinetic Conflict-Free Coloring of Intervals with Respect to Points de Berg, Mark Leijsen, Tim Markovic, Aleksandar van Renssen, André Roeloffzen, Marcel Woeginger, Gerhard Conflict-free colorings Dynamic data structures Kinetic data structures We introduce the fully-dynamic conflict-free coloring problem for a set S of intervals in R^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 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mark de Berg and Tim Leijsen and Aleksandar Markovic and André van Renssen and Marcel Roeloffzen and Gerhard Woeginger 2017 Is Part Of LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2017.26 urn:nbn:de:0030-drops-82683 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.26 eng https://creativecommons.org/licenses/by/3.0/legalcode