Given a set V of n points in k-dimensional space, and an Lq-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 Lq. This paper gives an O(nlogn) algorithm for the all-nearest-neighbors problem, for fixed dimension k and fixed metric Lq. Since there is an ¦[(nlogn) 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 the present algorithm is optimal up to a constant factor.
