arXiv preprint ·
Implicit Additively Weighted Geodesic Voronoi Diagrams and Applications
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
Let $P$ be a simple polygon with $m$ vertices. After $O(m)$-time preprocessing of $P$, for any set $S$ of $n$ additively weighted point sites, we compute an implicit additively weighted geodesic Voronoi diagram in $O(n\log n+n\log^2 m)$ time, supporting nearest-neighbor queries in $O(\log(n+m))$ time. In contrast, explicitly constructing the diagram requires $Ω(m)$ time. Our algorithm introduces a new sweep-line paradigm that avoids explicitly constructing the diagram, together with a novel technique for point location in implicit subdivisions. As applications, we obtain new dynamic data structures for additively weighted geodesic nearest-neighbor searching and the first efficient algorithms for shortest paths in geodesic disk graphs. After the same $O(m)$-time preprocessing, single-source shortest paths in a geodesic disk graph of $n$ sites can be computed in $O(n\log n+n\log^2 m)$ time in the unweighted case and $O(n^{3/2}(\log n+\log^2 m))$ time in the weighted case. We also extend our techniques to implicit farthest geodesic Voronoi diagrams for unweighted sites, obtaining analogous bounds and dynamic farthest-neighbor data structures.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Computational Geometry
Optimal Average Distortion for Non-Expansive Embeddings of Euclidean Metrics into the Line: With applications to cut-matching games and vertex expansion
Representation-Aware Closed-Surface Parameterization: Exact Sensitivity Analysis and Pole-Aware Planar Preconditioning
CuPH: Parallel Cubical Persistent Homology via Level-Synchronous Component Tracking
Catenary Visibility: A Geometric Framework for Planning with Tethered Robots
An $\mathsf{FPRAS}$ for Mixed Volumes
Get the few papers worth your time in Computational Geometry every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.