CS Paper Radar

Implicit Additively Weighted Geodesic Voronoi Diagrams and Applications

Bruce W. Brewer, Haitao Wang

cs.CG cs.DS ·submitted 2026-10-30 17:31 UTC · v1
top venue

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.

Comment
To appear in SODA 2027

Closest papers

Nearest neighbours by meaning across the whole index.

Optimal Planar $k$ Nearest Neighbors Queries for Additively Weighted Euclidean Distances and Convex Metrics

cs.CG ·2026-10-12 ·Chih-Hung Liu
top venuetheory similarity 0.65
Abstract · 78 pages. A conference version will appear in the Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA 2027)

Given a set $P$ of $n$ point sites in the plane, the $k$ nearest neighbors problem is to build a data structure that, for a query point $v$ and a query integer $k$, reports the $k$ nearest point sites of $v$ in $P$ efficiently. For the Euclidean metric, after four decades of efforts, an optimal data structure has been developed with $O(n)$ space, $O(\log n+k)$ query time and $O(n\log n)$ preprocessing time [Mat92b, Cha00, AC09, CT16]. In contrast, for a family of distance functions, the state-of-the-art data structure [AES99, KMR+20, Liu22] attains $O(n\log\log n)$ space, $O(\log n+k)$ query time and expected $O(n\log n)$ preprocessing time. An open question is the existence of an optimal data structure with $O(n)$ space and $O(\log n + k)$ query time for distance functions more general than the Euclidean metric. Such an optimal data structure also remains unknown for non-point sites in the Euclidean metric, even for disk sites or, more generally, additively weighted Euclidean distances. We develop an optimal $k$-nearest-neighbors data structure for additively weighted Euclidean distances with $O(n)$ space, $O(\log n + k)$ query time and expected $O(n\log n)$ preprocessing time. Since this data structure can be adjusted to disk sites, it serves as an initial result toward optimality for non-point sites. We also adapt our data structure to point sites under a family of convex metrics, including commonly used $L_p$ metrics and uniform orientation metrics. The data structure can be further extended to distance functions that satisfy certain axioms. Thus, we demonstrate the existence of optimal $k$-nearest-neighbors data structures for distance functions more general than point sites in the Euclidean metric. Our main technical advance is to generalize Matoušek's shallow partition theorem for hyperplanes [Mat92b] to these settings, while achieving a logarithmic crossing number.

0.42

Geo-Filtered Approximate Nearest-Neighbor Search on a Single Proximity Graph

cs.DB ·2026-10-25 ·Zhiqiu Zou, Rong-Hua Li, Qiangqiang Dai, Guoren Wang
theory similarity 0.63
Abstract · 15 pages, 9 figures, 5 tables. Full version with appendix and proofs

Geo-filtered approximate nearest-neighbor (GFANN) search retrieves the objects inside a query-specified geographic disk whose feature vectors are closest to a query vector, a core operation in location-aware Web search. A disk filter on a standard proximity graph invalidates out-of-disk routing vertices; on selective disks, these removals break greedy paths and recall drops sharply. Existing methods scan all in-disk objects, over-fetch unfiltered candidates, or maintain separate sub-indexes across spatial partitions, trading latency for index overhead. We propose REACH, a single-graph index based on row-local active-order invariance: if every vertex stores its outgoing neighbors in a fixed-width row sorted by vector distance, any disk filter masks out-of-disk entries while surviving in-disk (active) neighbors remain vector-sorted. Offline, each vertex merges globally closest vector candidates with a nearest-first geographic stream into one row; online, beam search evaluates vector distances only for the first l active entries of each visited row. Because co-located objects share the same distance to every query center, every disk admits a coordinate group in full or not at all, decomposing active connectivity into intra-group and inter-coordinate conditions. Under a spatial marked-site model with repeated coordinates, we prove that polylogarithmic out-degree guarantees strong connectivity across all disks and constant-factor distance reduction per hop on compact disks, while a cut-rank threshold characterizes the minimum scan budget l. Across four datasets up to 10^7 objects, one REACH index per dataset outperforms SOTA methods, achieving 2.49x higher geometric-mean QPS than the strongest baseline at 0.95 Recall@10 on selective queries, while building 3.8x-11.9x faster and using 37%-45% less space than a SOTA spatial-graph index.

0.27

Delaunay-Based Nearest Neighbor Search with Grid-Accelerated Queries and Parallel Construction

cs.GR cs.CG ·2026-11-11 ·Pengfei Wang, Shiqing Xin, Changhe Tu
similarity 0.60
Abstract

Nearest-neighbor search is a fundamental primitive in computer graphics, with applications in distance field computation, surface reconstruction, and point cloud registration. In many graphics applications, data points lie on a surface manifold embedded in 3D space, whereas queries are distributed throughout the surrounding volume, a setting in which spatial partitioning structures such as k-d trees and grids can become inefficient. Dynamic-programming-based nearest-neighbor search (DP-NNS) offers an alternative: it traverses a successor DAG that records the history of incremental Delaunay construction and often outperforms spatial partitioning structures. However, its sequential construction is slow, and naive parallelization degrades query performance, limiting its practical adoption. We accelerate both queries and construction in DP-NNS. For queries, we introduce a grid-based initialization strategy that precomputes valid starting points on the successor DAG, shortening search paths while preserving exactness and enabling a twofold speedup. For construction, we analyze how parallel insertion affects query cost and develop a parallel algorithm that preserves logarithmic expected query cost under stated geometric assumptions. Our parallel construction algorithm achieves a 10x speedup over the sequential baseline while maintaining nearly the same query cost. We further reorder query points to improve cache locality. Extensive experiments demonstrate that our method outperforms widely used libraries in nearest-neighbor query performance.

0.14

Quadratic Complexity of Voronoi Diagrams in $\mathbb{R}^3$ for Lines in a Single Ruling of a Regulus

cs.CG math.AG ·2026-08-27 ·Eunku Park, Kangjin Han
theory similarity 0.60
Abstract · Added a coauthor, more detailed explanations of algebraic geometry, and additional figures

We study nearest and farthest Voronoi diagrams of lines in three-dimensional Euclidean space, which partition space according to the closest and farthest input lines, respectively. For arbitrary lines, a gap remains between the known quadratic lower bound and near-cubic upper bounds for the complexity of the nearest diagram. We consider input lines chosen from one of two continuous families of straight lines on a smooth surface defined by a quadratic equation, with one line from each family passing through every point of the surface. Under the geometric assumptions stated in the paper, we prove quadratic upper bounds on the total number of vertices, edges, faces, and connected three-dimensional regions in both diagrams. We also construct quadratically many nearest vertices using lines from a single family on one fixed surface, establishing a tight quadratic worst-case bound. The farthest diagram has quadratic total complexity for every input satisfying our assumptions. Our proof uses a parametrization that arranges the input lines in a cyclic order and expresses tangency to a sphere by a polynomial equation of degree four. At a Voronoi vertex, the four tangent input lines give four distinct roots. The sign changes between these roots, together with the nearest or farthest condition, force two intervening parameter intervals to contain no other input parameters. Thus, only quadratically many choices of four lines can define a vertex, and each choice yields at most eight isolated candidate centers.

0.27

Two-point Approximate Shortest Path Queries among Convex Polygonal Obstacles in the Plane

cs.CG ·2026-08-10 ·Siddharth Gaur, R. Inkulu
similarity 0.59
Abstract

Given a polygonal domain $\cal P$ consisting $h$ pairwise disjoint convex polygonal obstacles together defined with $n$ vertices and a positive real number $ε$ in $(0, 0.6)$, this paper presents an algorithm to preprocess $\cal P$ in $O(n+\frac{h}ε(h+\frac{1}{\sqrtε})\lg(\frac{h}{\sqrtε}))$ time to compute data structures of size $O(n+\frac{h}{\sqrtε} (h+\frac{1}ε))$ so that given any two points $s$ and $t$ in the free space defined by $\cal P$, a path between $s$ and $t$ with a $(1+ε)$ multiplicative stretch and $13\ell$ additive stretch is output in $O(\frac{1}{\sqrtε}(\lg{\frac{h}{\sqrtε}})+\frac{h}{ε^{2.5}}(\lg{\lg(\frac{h}{\sqrtε})}))$ time. Here, $\ell$ is upper bounded by $(\sqrt{2ε}) (\max_{P_i \in \cal P} \max_{p, q \in P_i} |pq|)$.

0.04

ToPos: Automated Optimal Positioning on Topographic Manifolds using Constrained Geodesic Voronoi Decomposition

cs.RO ·2026-09-04 ·Rajesh Raveendran, Akseli Vanhamaa, Jaakko Suutala, Antti Tikanmäki, Juha Röning
published similarity 0.59
Abstract · ©2026 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future m…

Reliable autonomous mapping, environmental sampling, last-mile logistics, and infrastructure deployment depend on the optimal surface area-balanced distribution of Spatial Reference Sites (SRS). Conventional 2D Euclidean methods often fail in high-relief environments by neglecting topographic variations and physical obstructions. This leads to significant planimetric distortion, spatial clustering, and the placement of targets in inaccessible or shadowed regions, compromising both data integrity and operational safety. This paper introduces ToPos, an automated framework for TOPography-aware Optimal Sampling on topographic manifolds. We treat the terrain as a discrete 2-dimensional manifold embedded in 3D Euclidean space and replace standard flat-map distances with non-Euclidean geodesic distances that follow the actual surface geometry. The point distribution is formulated as an optimization problem using a Constrained Geodesic Voronoi Decomposition, solved via a Riemannian Nesterov Accelerated Gradient (NAG) engine. Our approach restricts target locations to a feasible "safe zone," accounting for non-traversable slopes, vegetation, environmental occlusions, etc. Through evaluations on non-convex sinusoidal manifolds, we show that ToPos mitigates planimetric distortion by utilizing geodesic metrics. This approach results in a $\sim$74% improvement in optimal surface area-balanced distribution, as measured by the coefficient of variation (CV) of the Voronoi cell areas. The framework is architected as a Geographic Information System (GIS)-ready micro-service to bolster the mentioned applications. Index Terms: Topographic Manifolds, Geodesic Voronoi Decomposition, Infrastructure Deployment, 3D Mapping, Spatial Sampling, and Non-Euclidean Optimization.

0.35

Towards Dynamic Top-$k$ Simple Shortest Paths

cs.DS ·2026-10-14 ·Gianlorenzo D'Angelo, Andrea D'Ascenzo, Mattia D'Emidio, Gabriele Di Stefano, Marta Innamorati
theory similarity 0.58
Abstract

Computing the top-$k$ \textit{simple} shortest paths between two vertices of a graph, i.e., solving the P-KSSP problem, is a fundamental primitive in graph analytics. In modern scenarios, however, queries are rarely one-shot: parameters change as applications adapt their information needs, and recomputing a solution from scratch at every request quickly becomes a bottleneck. We study P-KSSP in a dynamic setting, focusing on changes of the parameter $k$: given a top-$k$ solution for a pair of vertices and a new value $k'$, the goal is to compute a top-$k'$ solution reusing the previously computed paths. Our approach rests on the \textit{pseudo-tree}, a compact representation of a collection of simple $s$--$t$ paths: we show that building it from an arbitrary, unstructured solution amounts to trie construction, and give two constructions running in time linear in the size of the collection. On top of it, we design UPD, a dynamic algorithm that updates a solution upon a change of $k$; we prove its correctness, analyze its complexity, and show that it is a general, solver-agnostic scheme, which starts from the paths alone, is parametric in the routine that generates candidate paths and combinable with known preprocessing techniques, as well as with an online pruning rule that we formalize. While a worst-case update is asymptotically comparable to recomputing from scratch, an extensive experimental evaluation shows that a variant of UPD is the fastest method in the large majority of tested configurations, often by a wide margin (with speedups over recomputation that grow with $k$ and $k'$ and exceed $60\times$), yielding a practical recipe for the configuration to deploy.

0.30

Constant Approximation of Fréchet Distance in Near-Linear Time

cs.CG ·2026-10-30 ·Haoqiang Huang, Zihe Wang, Shuo Zhang
similarity 0.58
Abstract

We give the first constant-factor approximation for the Fréchet distance in near-linear time. Given two polygonal curves in $\mathbb{R}^d$ with $n$ and $m$ vertices, respectively, where $m\le n$, our deterministic algorithm runs in $O(n^{1+\varepsilon})$ time for every fixed $\varepsilon>0$ and $d$, with an approximation factor depending only on $\varepsilon$ and $d$. The same result holds for the discrete Fréchet distance. Our result extends the line of work initiated by Cheng, Huang, and Zhang (STOC 2025) from strongly subquadratic to near-linear time. Our algorithm recursively balances preprocessing and query time. An index for comparing subcurves of a single curve supports faster queries between different curves. We obtain this speedup by replacing one curve with surrogates assembled from indexed subcurves of the other and shared across starting points of matchings. Faster queries then reduce the cost of building the next index. Compact boundary reachability summaries allow the answers to be reused in later recursive calls. After a number of rounds depending only on $\varepsilon$, both preprocessing and query time are near-linear.

0.15