Fully-dynamic and kinetic conflict-free coloring of intervals with respect to points

DOI10.4230/LIPICS.ISAAC.2017.26MaRDI QIDQ5136245zbMATH OpenOpenAlexFDO

Authors Tim Leijsen, Aleksandar Markovic, André van Renssen, Marcel Roeloffzen, Gerhard J. Woeginger, Mark de Berg

Publication date 25 November 2020

Full work available at URL https://arxiv.org/abs/1701.03388

zbMATH Keywords

dynamic data structureskinetic data structuresconflict-free colorings

Mathematics Subject Classification ID

Data structures (68P05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: We introduce the fully-dynamic conflict-free coloring problem for a set $S$ of intervals in $mathbb{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(logn/loglogn)$, and that any strategy using $O(1/varepsilon)$ colors needs $Omega(varepsilon{n}^{varepsilon})$ recolorings; - a coloring strategy that uses $O(logn)$ colors at the cost of $O(logn)$ recolorings, and another strategy that uses $O(1/varepsilon)$ colors at the cost of $O(n^{varepsilon}/varepsilon)$ 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.

Recommendations

• Fully-Dynamic and Kinetic Conflict-Free Coloring of Intervals with Respect to Points
• Dynamic conflict-free colorings in the plane
• Dynamic conflict-free colorings in the plane
• Online Conflict‐Free Coloring for Intervals
• Online conflict-free coloring for intervals

Cites work

• scientific article; zbMATH DE number 5506191 (Why is no real title available?)
• Computational geometry. Algorithms and applications.
• Conflict-Free Colorings of Simple Geometric Regions with Applications to Frequency Assignment in Cellular Networks
• Conflict-free coloring and its applications
• Conflict-free coloring made stronger
• Conflict-free coloring of points and simple regions in the plane
• Deterministic conflict-free coloring for intervals: from offline to online
• Introduction to algorithms.
• On conflict-free multi-coloring
• Online conflict-free coloring for intervals
• Online conflict-free colouring for hypergraphs
• Strong conflict-free coloring for intervals

Cited in

(6)

• Dynamic conflict-free colorings in the plane
• Fully-Dynamic and Kinetic Conflict-Free Coloring of Intervals with Respect to Points
• Conflict-free coloring of points on a line with respect to a set of intervals
• On conflict-free coloring of points and simple regions in the plane
• Dynamic conflict-free colorings in the plane
• Dynamic data structures for interval coloring

This page was built for publication: Fully-dynamic and kinetic conflict-free coloring of intervals with respect to points

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5136245)