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:
- The set is dynamic: Sites are frequently inserted and deleted.
- The metrics are non-Euclidean: Using $L_p$-norms or additively weighted distances.
- 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.
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.
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