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