In-place 2-d nearest neighbor search

Timothy M. Chan, Eric Y. Chen

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.

Original languageEnglish (US)
Title of host publicationProceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms
Number of pages8
StatePublished - 2008
Externally publishedYes
Event19th Annual ACM-SIAM Symposium on Discrete Algorithms - San Francisco, CA, United States
Duration: Jan 20 2008Jan 22 2008

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms


Other19th Annual ACM-SIAM Symposium on Discrete Algorithms
Country/TerritoryUnited States
CitySan Francisco, CA

ASJC Scopus subject areas

  • Software
  • Mathematics(all)


Dive into the research topics of 'In-place 2-d nearest neighbor search'. Together they form a unique fingerprint.

Cite this