Kinetic Geodesic Voronoi Diagrams in a Simple Polygon

Authors:

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.
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: