Kinetic Geodesic Voronoi Diagrams in a Simple Polygon
- 12 October 2023
- journal article
- research article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 37 (4) , 2276-2311
Abstract
We study the geodesic Voronoi diagram of a set [Formula: see text] of [Formula: see text] linearly moving sites inside a static simple polygon [Formula: see text] with [Formula: see text] 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 [Formula: see text], and that this is tight in the worst case. Moreover, we develop compact, responsive, local, and efficient KDSs for both structures. Our data structures use linear space and process a worst-case optimal number of events. Our bisector and Voronoi center KDSs handle each event in [Formula: see text] 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
Funding Information
- Collaborative Research Based on Industrial Demand (17K12635)
- Exploratory Research for Advanced Technology (JPMJER1201)
- National Science Foundation (CCF-1422311)
- Nederlandse Organisatie voor Wetenschappelijk Onderzoek (612.001.651)
This publication has 27 references indexed in Scilit:
- Realistic Input Models for Geometric AlgorithmsAlgorithmica, 2002
- Randomized fully dynamic graph algorithms with polylogarithmic time per operationJournal of the ACM, 1999
- Data Structures for Mobile DataJournal of Algorithms, 1999
- An Optimal Algorithm for Euclidean Shortest Paths in the PlaneSIAM Journal on Computing, 1999
- A new algorithm for shortest paths among obstacles in the planeAnnals of Mathematics and Artificial Intelligence, 1991
- Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithmsACM Transactions on Graphics, 1990
- On the geodesic voronoi diagram of point sites in a simple polygonAlgorithmica, 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
- A data structure for dynamic treesJournal of Computer and System Sciences, 1983