New upper bounds for neighbor searching

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

Research output: Contribution to journalArticlepeer-review


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 - 1986

ASJC Scopus subject areas

  • General Engineering


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

Cite this