Optimal Expected-Time Algorithms for Closest-Point Problems

Geometric closest-point problems deal with the proximity relationships in k-dimensional point sets. Examples of closest-point problems include building minimum spanning trees, nearest neighbor searching, and triangulation construction. Shamos and Hoey 1975 have shown how the Voronoi diagram can be used to solve a number of planar closest-point problems in optimal worst-case time. In this paper we extend their work by giving optimal expected-time algorithms for solving a number of closest-point problems in k- space, including nearest neighbor searching, finding all nearest neighbors, and computing planar minimum spanning trees. In addition to establishing theoretical bounds, the algorithms in this paper can be implemented to solve practical problems very efficiently.