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

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

Abstract

We present a new data structure for dynamic nearest neighbor queries in the plane supporting a general family of distance functions, including $L_p$-norms and additively weighted Euclidean distances. Our structure handles general sites (points, line segments, disks) with constant description complexity. Utilizing $O(n \log^3 n)$ storage, it achieves polylogarithmic update and query times, a significant improvement over the previous $O(n^\epsilon)$ state-of-the-art. Applications include faster algorithms for dynamic minimum spanning trees, disk graph connectivity, and spanner construction in disk intersection graphs.

TL;DR

This research achieves a long-sought breakthrough in computational geometry: a data structure for dynamic nearest neighbor queries in the plane that works for general distance functions with polylogarithmic update and query times. By generalizing "vertical shallow cuttings" to complex algebraic surfaces, the authors replace previous $O(n^\epsilon)$ bottlenecks with much faster algorithms.

The Challenge of Dynamic General Metrics

Nearest neighbor searching is a fundamental problem. While static Euclidean point sets are well-handled with $O(\log n)$ query times, the problem becomes significantly more complex when:

  1. The set is dynamic: Sites are frequently inserted and deleted.
  2. The metrics are non-Euclidean: Using $L_p$-norms or additively weighted distances.
  3. The sites are complex: Handling line segments, disks, or convex polygons instead of simple points.

For decades, the standard for this general setting was an $O(n^\epsilon)$ update time. While sublinear, $n^\epsilon$ scales poorly compared to polylogarithmic functions, creating a major bottleneck for large-scale applications like dynamic matching or shortest-path trees in disk graphs.

Methodology: Bridging the Gap

The authors bridge this gap by combining and extending several sophisticated geometric techniques into a unified pipeline.

Algorithmic pipeline for constructing dynamic nearest neighbor data structures.

Key components of this approach include:

  • Vertical Shallow Cuttings for Surfaces: This is the "geometric engine." The authors extend shallow cuttings—regions covering the lowest levels of an arrangement—from planes to bivariate algebraic surfaces. Crucially, they prove these cuttings can be "vertical" (prismatic), which is essential for the ray-shooting queries used in Voronoi diagrams.
  • Randomized Incremental Construction (RIC): A new RIC algorithm computes the lowest $k$ levels of an arrangement efficiently. The authors also provide a tighter bound on the combinatorial complexity of these levels, improving previous results by a factor of $k^\epsilon$.
  • Improved Chan’s Structure: The paper revisits Timothy Chan’s "lookahead deletion" mechanism for planes and adapts it for general surfaces. In the process, they improve the original deletion time for planes by a factor of $\log n$.

Key Results and Impact

The paper provides a massive upgrade to the complexity bounds of several fundamental problems, moving from polynomial ($n^\epsilon$) to polylogarithmic complexity.

Comparison of complexity bounds between previous state-of-the-art and the new results.

Beyond the problems listed in the table above, the data structure enables significant improvements in other areas:

  • Dynamic MST ($L_p$-metric): Update time reduced to $O(\log^{11} n)$.
  • Disk Graph Connectivity: Update time improved to $O(\Psi^2 \log^9 n)$, where $\Psi$ is the ratio between maximum and minimum disk radii.
  • Dynamic Nearest Neighbor: General polylogarithmic update times for complex sites.

Limitations and Future Work

While theoretically superior, the high exponents on the logarithmic factors (e.g., $\log^9 n$ or $\log^{11} n$) mean these algorithms may require very large datasets to outperform simpler $O(n^\epsilon)$ approaches in practice. Furthermore, implementation is non-trivial, requiring robust algebraic kernels to handle surface intersections. Future research may focus on reducing these logarithmic factors and removing the dependency on the radius ratio $\Psi$ in disk graph applications.

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$$ 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)$$ O ( n log 3 n ) storage, and requires polylogarithmic update and query time, improving an earlier data structure of Agarwal, Efrat, and Sharir which required $$O(n^{\varepsilon })$$ O ( n ε ) time for an update and $$O(\log n)$$ 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 })$$ O ( n ε ) 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. To obtain this data structure, we combine and extend various techniques from the literature. Along the way, we obtain several side results that are of independent interest. Our data structure depends on the existence and an efficient construction of “vertical” shallow cuttings in arrangements of bivariate algebraic functions. We prove that an appropriate level in an arrangement of a random sample of a suitable size provides such a cutting. To compute it efficiently, we develop a randomized incremental construction algorithm for computing the lowest k levels in an arrangement of bivariate algebraic functions (we mostly consider here collections of functions whose lower envelope has linear complexity, as is the case in the dynamic nearest-neighbor context, under both types of norm). To analyze this algorithm, we also improve a longstanding bound on the combinatorial complexity of the vertical decomposition of these levels. Finally, to obtain our structure, we combine our vertical shallow cutting construction with Chan’s algorithm for efficiently maintaining the lower envelope of a dynamic set of planes in $${{\mathbb {R}}}^3$$ R 3 . Along the way, we also revisit Chan’s technique and present a variant that uses a single binary counter, with a simpler analysis and improved amortized deletion time (by a logarithmic factor; the insertion and query costs remain asymptotically the same).
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