An optimal algorithm for the all-nearest-neighbors problem

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. We give an O(nlogn) algorithm for the All-Nearest-Neighbors problem, for fixed dimension k and fixed metric Lq. Since there is an Ω(n logn) 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 upto a constant.