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

M.T. de Berg, T. Leijsen, A. Markovic, A.M. van Renssen, M.J.M. Roeloffzen, G. Woeginger

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

1 Citation (Scopus)

Abstract

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.
Original languageEnglish
Title of host publicationISAAC 2017 : 28th International Symposium on Algorithms and Computation, 9-12 December 2017, Phuket, Thailand
EditorsTakeshi Tokuyama, Yoshio Okamoto
Place of PublicationDagstuhl
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Pages26:1-26:13
ISBN (Electronic)9783959770545
ISBN (Print)978-3-95977-054-5
DOIs
Publication statusPublished - 1 Dec 2017
Event28th International Symposium on Algorithms and Computation (ISAAC 2017) - Phuket, Thailand
Duration: 9 Dec 201712 Dec 2017
Conference number: 28
http://aiat.in.th/isaac2017/

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume92
ISSN (Print)1868-8969

Conference

Conference28th International Symposium on Algorithms and Computation (ISAAC 2017)
Abbreviated titleISAAC 2017
CountryThailand
CityPhuket
Period9/12/1712/12/17
Internet address

Keywords

  • Conflict-free colorings
  • Dynamic data structures
  • Kinetic data structures

Fingerprint Dive into the research topics of 'Fully-dynamic and kinetic conflict-free coloring of intervals with respect to points'. Together they form a unique fingerprint.

Cite this