Dynamic Planar Voronoi Diagrams for General Distance Functions and their Algorithmic Applications

Haim Kaplan, Wolfgang Mulzer, Liam Roditty, Paul Seiferth, Micha Sharir

Abstract

We describe a new data structure for dynamic nearest neighbor queries in the plane with respect to a general family of distance functions. These include $L_p$-norms and additively weighted Euclidean distances. Our data structure supports general (convex, pairwise disjoint) sites that have constant description complexity (e.g., points, line segments, disks, etc.). Our structure uses $O(n \log^3 n)$ storage, and requires polylogarithmic update and query time, improving an earlier data structure of Agarwal, Efrat and Sharir that required $O(n^\varepsilon)$ time for an update and $O(\log n)$ time for a query [SICOMP, 1999]. Our data structure has numerous applications. In all of them, it gives faster algorithms, typically reducing an $O(n^\varepsilon)$ factor in the previous bounds to polylogarithmic. In addition, we give here two new applications: an efficient construction of a spanner in a disk intersection graph, and a data structure for efficient connectivity queries in a dynamic disk graph.

Introduction: Breaking the $O(n^\epsilon)$ Barrier

Nearest neighbor (NN) search is a cornerstone of computational geometry: given a set of "sites" (points, segments, or disks), find the one closest to a query point. While this is well-solved for static sets in Euclidean space, the "dynamic" version—where sites are frequently inserted or deleted—is much harder, especially when using non-standard distance functions.

For over 20 years, the state-of-the-art for general distance functions (like additively weighted distances or $L_\infty$ metrics) was stuck at an update time of $O(n^\epsilon)$, where $\epsilon$ is a small positive constant. While $n^\epsilon$ looks small, it grows significantly with $n$ compared to logarithmic functions. The gap was a lack of efficient "shallow cuttings" for complex 3D surfaces, which are the geometric tools needed to track the "closest" site as the set changes.

Methods

The authors transform the 2D nearest neighbor problem into a 3D problem: finding the lower envelope of a set of bivariate algebraic functions. To maintain this envelope dynamically, they combine several sophisticated techniques:

  1. Vertical Shallow Cuttings: They prove the existence of and provide a construction for "vertical" shallow cuttings for bivariate algebraic surfaces. These partition the space below the $k$-th level of a surface arrangement into a small number of simple cells.
  2. Randomized Incremental Construction (RIC): They develop a new RIC algorithm to compute the lowest $k$ levels of an arrangement of surfaces, allowing them to build the necessary cuttings and their "conflict lists" efficiently.
  3. Improved Chan’s Technique: They adapt Timothy Chan’s "deletion lookahead" mechanism—originally for flat planes—to work with curved algebraic surfaces, shaving off a logarithmic factor from the original deletion time.
  4. Bentley-Saxe Transformation: They use a variant of this classic "static-to-dynamic" transformation to handle insertions using a series of binary-sized static structures.
The methodological pipeline for constructing dynamic lower envelopes for surfaces and their subsequent applications.

Key Insights and Ideas

  • Complexity of the $k$-level: The authors improve the known bound on the combinatorial complexity of the vertical decomposition of the $k$ shallowest levels in an arrangement of surfaces, moving from $O(nk^{2+\epsilon})$ to a tighter $O(nk\lambda_s(k))$, where $\lambda_s$ is a nearly linear function related to Davenport-Schinzel sequences.
  • The "Vertical" Requirement: Previous shallow cuttings for general surfaces weren't "vertical" (semi-unbounded prisms), making them incompatible with efficient point-location structures. The authors show that by using random sampling and relative $(p, \epsilon)$-approximations, they can force the cuttings to be vertical.
  • Combinatorial Generality: The framework is "purely combinatorial." As long as the distance function and the sites have "constant description complexity," the polylogarithmic bounds hold.

Key Results and Applications

The paper achieves a massive theoretical speedup for dynamic nearest neighbor queries and its applications. The new data structure uses $O(n \log^3 n)$ storage and supports queries in $O(\log^2 n)$ time. Insertions take $O(\log^5 n \lambda_s(\log n))$ and deletions take $O(\log^9 n \lambda_s(\log n))$ amortized expected time.

Comparison of previous $O(n^\epsilon)$ bounds versus the new polylogarithmic bounds for various geometric problems.

Key application improvements include:

  • Dynamic Connectivity in Disk Graphs: For disks with radii in a fixed range $[1, \Psi]$, the update time drops from $O(n^{20/21})$ to $O(\Psi^2 \log^9 n \dots)$.
  • Bichromatic Closest Pair: For general planar metrics, the update time is reduced from $O(n^\epsilon)$ to polylogarithmic factors.
  • Spanners: A new algorithm for $(1+\rho)$-spanners in disk intersection graphs runs in nearly linear time, independent of the radius ratio.

Limitations and Future Work

While "polylogarithmic" is a major theoretical win over $n^\epsilon$, the exponents are high (up to $\log^9 n$ or $\log^{11} n$). This suggests the constants might be too large for the algorithm to be practical for small-to-medium datasets without further optimization. Additionally, most update bounds are amortized and expected; developing deterministic, worst-case polylogarithmic updates remains an open challenge.

Summary updated

Abstract

We describe a new data structure for dynamic nearest neighbor queries in the plane with respect to a general family of distance functions. These include $L_p$-norms and additively weighted Euclidean distances. Our data structure supports general (convex, pairwise disjoint) sites that have constant description complexity (e.g., points, line segments, disks, etc.). Our structure uses $O(n \log^3 n)$ storage, and requires polylogarithmic update and query time, improving an earlier data structure of Agarwal, Efrat and Sharir that required $O(n^\varepsilon)$ time for an update and $O(\log n)$ time for a query [SICOMP, 1999]. Our data structure has numerous applications. In all of them, it gives faster algorithms, typically reducing an $O(n^\varepsilon)$ factor in the previous bounds to polylogarithmic. In addition, we give here two new applications: an efficient construction of a spanner in a disk intersection graph, and a data structure for efficient connectivity queries in a dynamic disk graph.
BibTeX
@inproceedings{kaplan2017dynamic,
  author = {Haim Kaplan and Wolfgang Mulzer and Liam Roditty and Paul Seiferth and Micha Sharir},
  title = {{Dynamic Planar Voronoi Diagrams for General Distance Functions and their Algorithmic Applications}},
  booktitle = {SODA},
  year = {2017},
  doi = {10.1137/1.9781611974782.165},
}
Figure