An O(n log n) algorithm for the all-nearest-neighbors problem
From MaRDI portal
Publication:1115187
DOI10.1007/BF02187718zbMath0663.68058WikidataQ29396159 ScholiaQ29396159MaRDI QIDQ1115187
Publication date: 1989
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://eudml.org/doc/131067
Minkowski metriccomputational geometryalgebraic decision-tree model of computationall-nearest-neighbors problem
Analysis of algorithms and problem complexity (68Q25) Computing methodologies and applications (68U99) General theory of distance geometry (51K05)
Related Items (44)
Iterated nearest neighbors and finding minimal polytopes ⋮ An optimal algorithm for the on-line closest-pair problem ⋮ Kinetic \(k\)-semi-Yao graph and its applications ⋮ Selection in monotone matrices and computing k th nearest neighbors ⋮ An approach to adaptive refinement for the RBF-FD method for 2D elliptic equations ⋮ A dynamic separator algorithm ⋮ A plane-sweep algorithm for the all-nearest-neighbors problem for a set of convex planar objects ⋮ On nearest-neighbor graphs ⋮ A Low Arithmetic-Degree Algorithm for Computing Proximity Graphs ⋮ Attributed relational graph matching based on the nested assignment structure ⋮ Minimum dilation stars ⋮ Algorithms for proximity problems in higher dimensions ⋮ An adaptive well-balanced positivity preserving central-upwind scheme on quadtree grids for shallow water equations ⋮ Kinetic Reverse k-Nearest Neighbor Problem ⋮ A taxonomy for nearest neighbour queries in spatial databases ⋮ Computing farthest neighbors on a convex polytope. ⋮ Diffusion polynomial frames on metric measure spaces ⋮ Approximate $k$-Nearest Neighbor Graph on Moving Points ⋮ Minimizing interference in ad hoc networks with bounded communication radius ⋮ REVERSE NEAREST NEIGHBOR QUERIES IN FIXED DIMENSION ⋮ Maintaining the minimal distance of a point set in polylogarithmic time ⋮ Farthest neighbors, maximum spanning trees and related problems in higher dimensions ⋮ An all-round sweep algorithm for 2-dimensional nearest-neighbor problems ⋮ Provably Good Partitioning and Load Balancing Algorithms for Parallel Adaptive N-Body Simulation ⋮ Dispersion in disks ⋮ Approximate closest-point queries in high dimensions ⋮ Farthest-point queries with geometric and combinatorial constraints ⋮ Sigma-local graphs ⋮ ON ENUMERATING AND SELECTING DISTANCES ⋮ MIXED SPANNING TREES IN THEORY AND PRACTICE ⋮ Ramsey partitions and proximity data structures ⋮ Efficient approximation algorithms for clustering point-sets ⋮ Region-fault tolerant geometric spanners ⋮ A sparse graph almost as good as the complete graph on points in \(k\) dimensions ⋮ The Weak Gap Property in Metric Spaces of Bounded Doubling Dimension ⋮ Faster DBSCAN and HDBSCAN in Low-Dimensional Euclidean Spaces ⋮ Multidimensional phase recovery and interpolative decomposition butterfly factorization ⋮ Tight bounds on the solutions of multidimensional divide-and-conquer maximin recurrences ⋮ Extending range queries and nearest neighbors ⋮ Chromatic nearest neighbor searching: A query sensitive approach ⋮ Approximate range searching ⋮ On Some Proximity Problems of Colored Sets ⋮ Approximating Euclidean distances by small degree graphs ⋮ Faster DBScan and HDBScan in Low-Dimensional Euclidean Spaces
Cites Work
This page was built for publication: An O(n log n) algorithm for the all-nearest-neighbors problem
