In-place 2-d nearest neighbor search

We revisit a classic problem in computational geometry: preprocessing a planar n-point set to answer nearest neighbor queries. In SoCG 2004, Brönnimann, Chan, and Chen showed that it is possible to design an efficient data structure that takes no extra space at all other than the input array holding a permutation of the points. The best query time known for such "in-place data structures" is O(log² n). In this paper, we break the O(log² n) barrier by providing a method that answers nearest neighbor queries in time O((log n)^log3/22log log n) = O(log^1.71 n). The new method uses divide-and-conquer (based on planar separators) in a way that is quite unlike traditional point location methods, and extends previous 1-d data structuring techniques (specifically the van Emde Boas layout). The method has further applications, for example, in answering extreme point queries for a 3-d point set on the boundary of a convex set of constant complexity.