Kinetic Geodesic Voronoi Diagrams in a Simple Polygon

DOI10.1137/20M1384804MaRDI QIDQ6057802zbMATH OpenOpenAlexFDO

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

Publication date 26 October 2023

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2002.05910

zbMATH Keywords

computational geometrygeodesic distancesimple polygonkinetic data structuregeodesic Voronoi diagram

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Data structures (68P05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

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(lo{g}^{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.

Cites work

• scientific article; zbMATH DE number 732977 (Why is no real title available?)
• scientific article; zbMATH DE number 219238 (Why is no real title available?)
• scientific article; zbMATH DE number 2107521 (Why is no real title available?)
• A data structure for dynamic trees
• A linear time algorithm for minimum link paths inside a simple polygon
• A nearly optimal algorithm for the geodesic Voronoi diagram of points in a simple polygon
• A new algorithm for shortest paths among obstacles in the plane
• A new approach for the geodesic Voronoi diagram of points in a simple polygon and other restricted polygonal domains
• An Optimal Algorithm for Euclidean Shortest Paths in the Plane
• Computational geometry. Algorithms and applications.
• Computing the geodesic center of a simple polygon
• Computing the geodesic centers of a polygonal domain
• Data Structures for Mobile Data
• Geodesic-preserving polygon simplification
• Improved dynamic geodesic nearest neighbor searching in a simple polygon
• Kinetic Voronoi diagrams and Delaunay triangulations under polygonal distance functions
• Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
• On kinetic Delaunay triangulations: a near-quadratic bound for unit speed motions
• On the geodesic Voronoi diagram of point sites in a simple polygon
• Optimal algorithm for geodesic nearest-point Voronoi diagrams in simple polygons
• Randomized fully dynamic graph algorithms with polylogarithmic time per operation
• Realistic input models for geometric algorithms
• Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms
• Static and kinetic geometric spanners with applications
• The furthest-site geodesic Voronoi diagram
• The geodesic 2-center problem in a simple polygon
• Visibility graphs, dismantlability, and the cops and robbers game
• Visibility queries and maintenance in simple polygons
• Voronoi diagrams for a moderate-sized point-set in a simple polygon

Cited in

(2)

• scientific article; zbMATH DE number 5220265 (Why is no real title available?)
• Kinetic stable Delaunay graphs

This page was built for publication: Kinetic Geodesic Voronoi Diagrams in a Simple Polygon

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6057802)