The complexity of finding fixed-radius near neighbors

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

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

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

algorithmcomplexity measurecomplexity measured as function of both input and output sizesfixed-radius near neighbors problem

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Analysis of algorithms (68W40) Nonparametric estimation (62G05) Symbolic computation and algebraic computation (68W30) Formal languages and automata (68Q45)

Related Items (18)

Linear-Time Approximation Algorithms for Unit Disk Graphs ⋮ Lagrangian numerical methods for ocean biogeochemical simulations ⋮ TWO-DIMENSIONAL RANGE SEARCH BASED ON THE VORONOI DIAGRAM ⋮ Inadequacy of linear methods for minimal sensor placement and feature selection in nonlinear systems: a new approach using secants ⋮ An O(n log n) algorithm for the all-nearest-neighbors problem ⋮ Algorithms for proximity problems in higher dimensions ⋮ The asymmetric particle population density method for simulation of coupled noisy oscillators ⋮ Shifting Coresets: Obtaining Linear-Time Approximations for Unit Disk Graphs and Other Geometric Intersection Graphs ⋮ Fixed-radius near neighbors search algorithms for points and segments ⋮ Efficient sub-5 approximations for minimum dominating sets in unit disk graphs ⋮ Low complexity methods for discretizing manifolds via Riesz energy minimization ⋮ Fast greedy triangulation algorithms. ⋮ Fast discrete convolution in \(\mathbb{R}^2\) with radial kernels using non-uniform fast Fourier transform with nonequispaced frequencies ⋮ A note on the graph isomorphism counting problem ⋮ Fast and scalable algorithms for constructing solvent-excluded surfaces of large biomolecules ⋮ Conformal actions of 𝔰𝔩_{𝔫}(ℝ) and 𝕊𝕃_{𝕟}(ℝ)⋉ℝⁿ on Lorentz manifolds ⋮ Reporting intersections among thick objects. ⋮ Evaluation of Range Searching Methods for Contact Searching in Mechanical Engineering

Cites Work

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

This page was built for publication: The complexity of finding fixed-radius near neighbors