An O(n log n) algorithm for the all-nearest-neighbors problem
From MaRDI portal
Given a set V of n points in k-dimensional space, and an \(L_ q\)-metric (Minkowski metric), the all-nearest-neighbors problem is defined as follows: for each point p in V, find all those points in V-\(\{\) \(p\}\) that are closest to p under the distance metric \(L_ q\). We give an O(n log n) algorithm for the all-nearest-neighbors problem, for fixed dimension k and fixed metric \(L_ q\). Since there is an \(\Omega\) (n log n) lower bound, in the algebraic decision-tree model of computation, on the time complexity of any algorithm that solves the all-nearest- neighbors problem (for \(k=1)\), the running time of our algorithm is optimal up to a constant factor.
Recommendations
- Probabilistic analysis of an algorithm for solving the \(k\)-dimensional all-nearest-neighbors problem by projection
- scientific article; zbMATH DE number 4074476
- The complexity of finding fixed-radius near neighbors
- Nearest neighbor queries in metric spaces
- scientific article; zbMATH DE number 437552
Cites work
- scientific article; zbMATH DE number 43279 (Why is no real title available?)
- scientific article; zbMATH DE number 3573250 (Why is no real title available?)
- scientific article; zbMATH DE number 3597592 (Why is no real title available?)
- Multidimensional divide-and-conquer
- Optimal Expected-Time Algorithms for Closest Point Problems
- The complexity of finding fixed-radius near neighbors
Cited in
(63)- Region-fault tolerant geometric spanners
- 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
- Approximate closest-point queries in high dimensions
- The complexity of finding fixed-radius near neighbors
- Approximating Euclidean distances by small degree graphs
- Iterated nearest neighbors and finding minimal polytopes
- An optimal algorithm for the on-line closest-pair problem
- A fast algorithm for k-nearest neighbor problem on a reconfigurable mesh computer
- On nearest-neighbor graphs
- Computing farthest neighbors on a convex polytope.
- Tight bounds on the solutions of multidimensional divide-and-conquer maximin recurrences
- Chromatic nearest neighbor searching: A query sensitive approach
- Approximate range searching
- Kinetic \(k\)-semi-Yao graph and its applications
- A sparse graph almost as good as the complete graph on points in \(k\) dimensions
- Extending range queries and nearest neighbors
- Algorithms for proximity problems in higher dimensions
- An approach to adaptive refinement for the RBF-FD method for 2D elliptic equations
- A true \(O(n\log{n})\) algorithm for the all-\(k\)-nearest-neighbors problem
- Sigma-local graphs
- An efficient \(O(1)\) time 3D all nearest neighbor algorithm from image processing perspective
- Diffusion polynomial frames on metric measure spaces
- Farthest-point queries with geometric and combinatorial constraints
- Attributed relational graph matching based on the nested assignment structure
- An adaptive well-balanced positivity preserving central-upwind scheme on quadtree grids for shallow water equations
- scientific article; zbMATH DE number 1696644 (Why is no real title available?)
- Time-space tradeoffs for all-nearest-larger-neighbors problems
- On some proximity problems of colored sets
- Kinetic reverse \(k\)-nearest neighbor problem
- REVERSE NEAREST NEIGHBOR QUERIES IN FIXED DIMENSION
- scientific article; zbMATH DE number 437530 (Why is no real title available?)
- The Weak Gap Property in Metric Spaces of Bounded Doubling Dimension
- scientific article; zbMATH DE number 3907781 (Why is no real title available?)
- scientific article; zbMATH DE number 4074476 (Why is no real title available?)
- A taxonomy for nearest neighbour queries in spatial databases
- SIMPLE ALGORITHMS FOR ENUMERATING INTERPOINT DISTANCES AND FINDING k NEAREST NEIGHBORS
- scientific article; zbMATH DE number 1256675 (Why is no real title available?)
- Provably Good Partitioning and Load Balancing Algorithms for Parallel Adaptive N-Body Simulation
- A low arithmetic-degree algorithm for computing proximity graphs
- ON ENUMERATING AND SELECTING DISTANCES
- MIXED SPANNING TREES IN THEORY AND PRACTICE
- Approximate $k$-Nearest Neighbor Graph on Moving Points
- Selection in monotone matrices and computing k th nearest neighbors
- A dynamic separator algorithm
- A plane-sweep algorithm for the all-nearest-neighbors problem for a set of convex planar objects
- Faster DBScan and HDBscan in low-dimensional Euclidean spaces
- Faster \textsc{dbscan} and \textsc{hdbscan} in low-dimensional Euclidean spaces
- A sweep algorithm and its implementation: The all-nearest-neighbors problem revisited
- Accelerated non-parametrics for cascades of Poisson processes
- Permutation and Grouping Methods for Sharpening Gaussian Process Approximations
- Decomposition of zero-dimensional persistence modules via rooted subsets
- An o(n n)-time approximation scheme for geometric many-to-many matching
- Dispersion in disks
- Fast approximation algorithms for Euclidean minimum weight perfect matching
- Fast approximation algorithms for Euclidean minimum weight perfect matching
- Efficient approximation algorithms for clustering point-sets
- Multidimensional phase recovery and interpolative decomposition butterfly factorization
- On the symmetric angle-restricted nearest neighbor problem
- Minimum dilation stars
- On the angle restricted nearest neighbor problem
- Ramsey partitions and proximity data structures
This page was built for publication: An O(n log n) algorithm for the all-nearest-neighbors problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1115187)
