An O(n log n) algorithm for the all-nearest-neighbors problem (Q1115187)

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.