Simple Algorithms for Enumerating Interpoint Distances and Finding K Nearest Neighbors. Dickerson, M.&nbsp;T., Drysdale, Scot, R., & Sack, J.- International Journal of Computational Geometry \& Applications, 02(03):221--239, World Scientific Publishing Company, September, 1992.
We present an O(n log n+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.
@article{ DICKERSON1992,
abstract = {We present an O(n log n+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.},
author = {Dickerson, Matthew T. and Drysdale, R.L. Scot and Sack, J̈{o}rg-Rüdiger},
doi = {10.1142/S0218195992000147},
issn = {0218-1959},
journal = {International Journal of Computational Geometry \& Applications},
keywords = {Algorithms,Delaunay triangulation,enumeration,nearest neighbors,selection},
language = {en},
month = {September},
number = {03},
pages = {221--239},
publisher = {World Scientific Publishing Company},
title = {{Simple Algorithms for Enumerating Interpoint Distances and Finding K Nearest Neighbors}},
url = {http://www.worldscientific.com/doi/abs/10.1142/S0218195992000147},
volume = {02},
year = {1992}
}