This paper, authored by Chih-Hung Liu from ETH Zürich, represents a significant theoretical leap in computational geometry, specifically targeting the $k$-nearest neighbors ($k$-NN) problem in two dimensions for general distance functions and non-point sites.
Abstract
We study the $k$ nearest neighbors problem in the plane for general, convex, pairwise disjoint sites of constant description complexity such as line segments, disks, and quadrilaterals and with respect to a general family of distance functions including the $L_p$-norms and additively weighted Euclidean distances. We develop a static data structure for the general setting with nearly optimal $O(n \log \log n)$ space, the optimal $O(\log n + k)$ query time, and expected $O(n \text{ polylog } n)$ preprocessing time. Our dynamic version also reduces the space of Kaplan et al.'s work from $O(n \log^3 n)$ to $O(n \log n)$. To obtain these progresses, we devise shallow cuttings of linear size for general distance functions using a new random sampling technique for the analysis of geometric structures.
The $k$-NN Problem in General Settings
The $k$-nearest neighbors problem is a cornerstone of computer science: given $n$ sites, find the $k$ closest ones to a query point. While this was solved optimally decades ago for points in Euclidean space ($O(n)$ space, $O(\log n + k)$ query time), real-world applications often involve non-point sites like line segments or disks and general distance functions like $L_p$-norms.
In these generalized settings, the "surfaces" representing distances become much more complex than simple planes. Previous state-of-the-art structures suffered from "space bloat," requiring $O(n \log^2 n)$ or $O(n \log^3 n)$ space to achieve fast query times. The challenge was to find a way to partition the space using "shallow cuttings" without the size of that partition exploding.
Methods: Linear-Size Shallow Cuttings
The author’s primary contribution is a new random sampling technique for analyzing geometric structures. A shallow cutting is a set of disjoint prisms that cover the "lower levels" of a distance arrangement. If one can build a small (linear-size) shallow cutting, they can limit the number of candidate sites a query needs to check.
The "Many Local Conflicts" Innovation
Standard geometric analysis often uses random sampling to show that if a configuration has few "global" conflicts, it likely has zero "local" conflicts. Liu flips this logic: he proves that if a configuration has many local conflicts, the probability that it has few global conflicts decreases factorially. This conceptual shift allows for a much tighter analysis of "relevant" prisms in a vertical decomposition, proving they can form a linear-size cutting $O(r)$ even for complex, non-linear distance surfaces.
Key Results and Impact
The paper provides new upper bounds for both static and dynamic $k$-NN data structures. The static structure achieves $O(n \log \log n)$ space with optimal $O(\log n + k)$ query time, while the dynamic version improves space to $O(n \log n)$.
As shown in the table above, these new bounds provide "direct hits" that improve existing algorithms for several fundamental problems:
- Dynamic Bichromatic Closest Pair: Space reduced from $O(n \log^3 n)$ to $O(n \log n)$.
- Dynamic MST in General Planar Metric: Space reduced from $O(n \log^5 n)$ to $O(n \log^3 n)$.
- Dynamic Intersection of Unit Balls in $\mathbb{R}^3$: Significant space and update time improvements.
Limitations and Future Work
While $O(n \log \log n)$ is "nearly optimal," the "holy grail" of $O(n)$ linear space for the static case under general distance functions remains elusive. The author notes that the Euclidean point-site solution relies on a "shallow partition theorem" that doesn't yet have a known general-distance analogue. Additionally, achieving the ideal $O(n \log n)$ preprocessing time remains a challenge, as current "traversal" methods for planes do not easily translate to pseudo-prisms.
Summary updated