Kinetic Geodesic Voronoi Diagrams in a Simple Polygon

Abstract

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(m^3)\), 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(\log^2 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.

Corresponding Publications

Kinetic Geodesic Voronoi Diagrams in a Simple Polygon

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

Proc. 47th International Colloquium on Automata, Languages and Programming, 2020

To Appear.
@incollection{kinetic_gvd2020,
  author = {Korman, Matias and van Renssen, Andr{\'e} and Roeloffzen, Marcel and Staals, Frank},
  title = {Kinetic Geodesic Voronoi Diagrams in a Simple Polygon},
  booktitle = {Proc. 47th International Colloquium on Automata, Languages and Programming},
  year = {2020},
  series = {Leibniz International Proceedings in Informatics (LIPIcs)},
  publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  location = {Saarbrücken, Germany (virtual conference)},
  category = {geodesic},
  note = {To Appear.},
}