The complexity of finding fixed-radius near neighbors

DOI10.1016/0020-0190(77)90070-9zbMath0373.68041WikidataQ29394334 ScholiaQ29394334MaRDI QIDQ1244819

Jon Louis Bentley, Donald F. Stanat, E. Hollins jun. Williams

Publication date: 1977

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(77)90070-9

zbMATH Keywords

algorithm; complexity measure; complexity measured as function of both input and output sizes; fixed-radius near neighbors problem

Mathematics Subject Classification ID

62H30: Classification and discrimination; cluster analysis (statistical aspects)

68W40: Analysis of algorithms

62G05: Nonparametric estimation

68W30: Symbolic computation and algebraic computation

68Q45: Formal languages and automata

Related Items

Conformal actions of 𝔰𝔩_{𝔫}(ℝ) and 𝕊𝕃_{𝕟}(ℝ)⋉ℝⁿ on Lorentz manifolds, Evaluation of Range Searching Methods for Contact Searching in Mechanical Engineering, TWO-DIMENSIONAL RANGE SEARCH BASED ON THE VORONOI DIAGRAM, Fixed-radius near neighbors search algorithms for points and segments, An O(n log n) algorithm for the all-nearest-neighbors problem, A note on the graph isomorphism counting problem, Reporting intersections among thick objects., Algorithms for proximity problems in higher dimensions, Fast greedy triangulation algorithms.

Cites Work

• Finding nearest neighbours
• Graph-Theoretical Methods for Detecting and Describing Gestalt Clusters
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item