Algorithms for proximity problems in higher dimensions.
M. T. Dickerson and D. Eppstein.
Comp. Geom. Theory & Applications 5: 277–291, 1996,
doi:10.1016/0925-7721(95)00009-7.
Combines a method from "Provably good mesh generation" for finding sparse high-dimensional Delaunay triangulations, a method of Dickerson, Drysdale, and Sack ["Simple algorithms for enumerating interpoint distances", IJCGA 1992] for using Delaunay triangulations to search for nearest neighbors, and a method of Frederickson for speeding up tree-based searches. The results are fast algorithms for several proximity problems such as finding the k nearest neighbors to each point in a given point set.
(Local copy of CGTA 1996 version of "algorithms for proximity problems")