Optimal Expected-Time Algorithms for Closest Point Problems
Jon Louis Bentley, Bruce W. Weide, Andrew Chi-Chih Yao · ACM Transactions on Mathematical Software · 1980
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.trinealgorithms 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.