New upper bounds for neighbor searching

B. Chazelle, R. Cole, F. P. Preparata, C. Yap

Research output: Contribution to journalArticle

32 Scopus citations


This paper investigates the circular retrieval problem and the k-nearest neighbor problem, for sets of n points in the Euclidean plane. Two similar data structures each solve both problems. A deterministic structure uses space O(n(log n log log n)2), and a probabilistic structure uses space O(n log2 n). For both problems, these two structures answer a query that returns k points in O(k + log n) time.

Original languageEnglish (US)
Pages (from-to)105-124
Number of pages20
JournalInformation and Control
Issue number1-3
StatePublished - Jan 1 1986
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Engineering(all)

Fingerprint Dive into the research topics of 'New upper bounds for neighbor searching'. Together they form a unique fingerprint.

Cite this