International Journal of Computational Geometry and Applications 2:3 (1992) 221-239.
Simple Algorithms for Enumerating Interpoint Distances and Finding k Nearest Neighbors
Matthew T. Dickerson, R.L.Drysdale, and J-R. Sack
Abstract
We present an O(n logn + k log k) time and O(n + k) space algorithm which
takes as input a set of n points in the plane and enumerates
the k smallest distances between pairs of points in nondecreasing
order. We also present an O(n log n + kn log k) solution to the problem of finding the k
nearest neighbors for each of n points.
Both algorithms are conceptually very simple,
are easy to implement, and are based on a common data structure: the
Delaunay triangulation.
Variants of the algorithms work for any convex distance function metric.
keywords:
algorithms, enumeration, selection, Delaunay triangulation,
nearest neighbors