@article{afbb375600c24f5d8e06c86dde5eb5fa,
title = "New upper bounds for neighbor searching",
abstract = "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.",
author = "B. Chazelle and R. Cole and Preparata, {F. P.} and C. Yap",
note = "Funding Information: * This research was supported in part by NSF Grants MCS 83-03925 and ONR and DARPA under contract N00014-83-K-0146 and ARPA Order 4786. * This work was done under the auspices of the NYU/CIMS Laboratory for Robotics and Experimental Computer Science, which is supported by grants from Digital Equipment Corporation, The Sloan Foundation, and ONR Grant N00014-82-K-0381. Also supported in part by NSF Grant DCR-84-01633 and by an IBM Faculty Development Award. ++T his research was supported in part by Joint Services Electronics Program under Contract N00014-79-C-0424.",
year = "1986",
doi = "10.1016/S0019-9958(86)80030-4",
language = "English (US)",
volume = "68",
pages = "105--124",
journal = "Information and Control",
issn = "0019-9958",
publisher = "Elsevier Inc.",
number = "1-3",
}