Optimal Expected-Time Algorithms for Closest Point Problems

Geometric closest potnt problems deal with the proxLmity relationships in k-dimensional point sets. Examples of closest point problems include building minimum spanning trees, nearest neighbor searching, and triangulation constructmn Shamos and Hoey [17] have shown how the Voronoi dtagram can be used to solve a number of planar closest point problems in optimal worst case tune. In this paper we extend thmr work by giving optimal expected.trine 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.