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

DOI10.4230/LIPICS.ISAAC.2017.26zbMATH Open1457.68284arXiv1701.03388OpenAlexW3005305494MaRDI QIDQ5136245FDOQ5136245

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

Publication date: 25 November 2020

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.

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

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

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)

Cites Work

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

Cited In (6)

• Dynamic conflict-free colorings in the plane
• Fully-Dynamic and Kinetic Conflict-Free Coloring of Intervals with Respect to Points
• On conflict-free coloring of points and simple regions in the plane
• Conflict-free coloring of points on a line with respect to a set of intervals
• 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)