On k Nearest Neighbor Queries in the Plane for General Distance Functions

Chih-Hung Liu

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.

Visualizing levels in a geometric arrangement and the resulting 3D prisms used for shallow cuttings.

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)$.

Comparison of old vs. new bounds for various dynamic geometric problems, showing significant reductions in space and update complexity.

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

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. For point sites in the Euclidean metric, after four decades of effort, an optimal data structure has recently been developed with O( n ) space, O( log n + k ) query time, and O( n log n ) preprocessing time. 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 polylog n ) preprocessing time. The O( n log log n ) space approaches the linear space, whose achievability is still unknown with the optimal query time, and improves the so far best O( n ( log^2 n )( log log n )^2 ) space of Bohler et al.'s work. Our dynamic version (that allows insertions and deletions of sites) 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. Shallow cuttings are a key technique to deal with the k nearest neighbors problem for point sites in the Euclidean metric. Agarwal et al. already designed linear-size shallow cuttings for general distance functions, but their shallow cuttings could not be applied to the k nearest neighbors problem. Recently, Kaplan et al. constructed shallow cuttings that are feasible for the k nearest neighbors problem, while the size of their shallow cuttings has an extra double logarithmic factor. Our innovation is a new random sampling technique for the analysis of geometric structures. Since our new technique provides a new way to develop and analyze geometric algorithms, we believe it is of independent interest.
BibTeX
@article{liu2020k,
  author = {Chih-Hung Liu},
  title = {{On k Nearest Neighbor Queries in the Plane for General Distance Functions}},
  journal = {SIAM Journal on Computing},
  year = {2020},
}
Figure