Nearly Optimal Planar k Nearest Neighbors Queries under General Distance Functions

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 Lp-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 [1,19]. 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 [12]. Our dynamic version (that allows insertions and deletions of sites) also reduces the space of Kaplan et al.'s work [33] from O(n log 3 n) to O(n log n) while keeping O(log 2 n + k) query time and O(polylog n) update time, thus improving many applications such as dynamic bichromatic closest pair and dynamic minimum spanning tree in general planar metric, and shortest path tree and dynamic connectivity in disk intersection graphs.

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. [4] 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. [33] 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. While our shallow cuttings seem, to some extent, merely a simple transformation of Agarwal et al.'s [4], the analysis requires our new technique to attain the linear size. Since our new technique provides a new way to develop and analyze geometric algorithms, we believe it is of independent interest.