Kinetic Geodesic Voronoi Diagrams in a Simple Polygon
Preprint
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 and Voronoi center kinetic data structures handle 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.
Keywords
All Related Versions
This publication has 16 references indexed in Scilit:
- Computing the geodesic centers of a polygonal domainComputational Geometry, 2019
- Voronoi Diagrams for a Moderate-Sized Point-Set in a Simple PolygonDiscrete & Computational Geometry, 2019
- The geodesic 2-center problem in a simple polygonComputational Geometry, 2018
- Visibility graphs, dismantlability, and the cops and robbers gameComputational Geometry, 2017
- Visibility Queries and Maintenance in Simple PolygonsDiscrete & Computational Geometry, 2002
- A New Approach for the Geodesic Voronoi Diagram of Points in a Simple Polygon and Other Restricted Polygonal DomainsAlgorithmica, 1998
- The furthest-site geodesic voronoi diagramDiscrete & Computational Geometry, 1993
- Computing the geodesic center of a simple polygonDiscrete & Computational Geometry, 1989
- Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygonsAlgorithmica, 1987
- A linear time algorithm for minimum link paths inside a simple polygonComputer Vision, Graphics, and Image Processing, 1986