TY - GEN

T1 - In-place 2-d nearest neighbor search

AU - Chan, Timothy M.

AU - Chen, Eric Y.

PY - 2008

Y1 - 2008

N2 - 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(log2 n). In this paper, we break the O(log2 n) barrier by providing a method that answers nearest neighbor queries in time O((log n)log3/22log log n) = O(log1.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.

AB - 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(log2 n). In this paper, we break the O(log2 n) barrier by providing a method that answers nearest neighbor queries in time O((log n)log3/22log log n) = O(log1.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.

UR - http://www.scopus.com/inward/record.url?scp=58449114903&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=58449114903&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:58449114903

SN - 9780898716474

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 904

EP - 911

BT - Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms

T2 - 19th Annual ACM-SIAM Symposium on Discrete Algorithms

Y2 - 20 January 2008 through 22 January 2008

ER -