New upper bounds for neighbor searching

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

doi:10.1016/S0019-9958(86)80030-4

New upper bounds for neighbor searching

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

Research output: Contribution to journal › Article › peer-review

42 Scopus citations

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)²), and a probabilistic structure uses space O(n log² n). For both problems, these two structures answer a query that returns k points in O(k + log n) time.

Original language	English (US)
Pages (from-to)	105-124
Number of pages	20
Journal	Information and control
Volume	68
Issue number	1-3
DOIs	https://doi.org/10.1016/S0019-9958(86)80030-4
State	Published - 1986
Externally published	Yes

All Science Journal Classification (ASJC) codes

General Engineering

Access to Document

10.1016/S0019-9958(86)80030-4

Cite this

@article{8af7705f5548445097cfbd29c37b3b2a,

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 = "Academic Press Inc.",

number = "1-3",

}

TY - JOUR

T1 - New upper bounds for neighbor searching

AU - Chazelle, B.

AU - Cole, R.

AU - Preparata, F. P.

AU - Yap, C.

N1 - 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.

PY - 1986

Y1 - 1986

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/0022453055

UR - https://www.scopus.com/pages/publications/0022453055#tab=citedBy

U2 - 10.1016/S0019-9958(86)80030-4

DO - 10.1016/S0019-9958(86)80030-4

M3 - Article

AN - SCOPUS:0022453055

SN - 0019-9958

VL - 68

SP - 105

EP - 124

JO - Information and control

JF - Information and control

IS - 1-3

ER -

New upper bounds for neighbor searching

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this