Kinetic geodesic Voronoi diagrams in a simple polygon

Matias Korman, André van Renssen, Marcel Roeloffzen, Frank Staals

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


We study the geodesic Voronoi diagram of a set S of n linearly moving sites inside a static simple polygon P with m vertices. We identify all events where the structure of the Voronoi diagram changes, bound the number of such events, and then develop a kinetic data structure (KDS) that maintains the geodesic Voronoi diagram as the sites move. To this end, we first analyze how often a single bisector, defined by two sites, or a single Voronoi center, defined by three sites, can change. For both these structures we prove that the number of such changes is at most O(m3), and that this is tight in the worst case. Moreover, we develop compact, responsive, local, and efficient kinetic data structures for both structures. Our data structures use linear space and process a worst-case optimal number of events. Our bisector KDS handles each event in O(log m) time, and our Voronoi center handles each event in O(log2 m) time. Both structures can be extended to efficiently support updating the movement of the sites as well. Using these data structures as building blocks we obtain a compact KDS for maintaining the full geodesic Voronoi diagram.

Original languageEnglish
Title of host publicationProc. 47th International Colloquium on Automata, Languages, and Programming (ICALP)
EditorsArtur Czumaj, Anuj Dawar, Emanuela Merelli
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
ISBN (Electronic)9783959771382
Publication statusPublished - 1 Jun 2020
Event47th International Colloquium on Automata, Languages, and Programming, ICALP 2020 - Virtual, Online, Germany
Duration: 8 Jul 202011 Jul 2020

Publication series

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


Conference47th International Colloquium on Automata, Languages, and Programming, ICALP 2020
CityVirtual, Online


  • Geodesic voronoi diagram
  • Kinetic data structure
  • Simple polygon


Dive into the research topics of 'Kinetic geodesic Voronoi diagrams in a simple polygon'. Together they form a unique fingerprint.

Cite this