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.
Cited by 315 works. doi:10.1145/355921.355927 Open-access PDF
Authors
References
- The Art of Computer Programming
- The Design and Analysis of Computer Algorithms
- An Algorithm for Finding Best Matches in Logarithmic Expected Time
- The Art of Computer Programming. Volume 1: Fundamental Algorithms.
- Closest-point problems
- Data Structures for Range Searching
- Convex hulls of finite sets of points in two and three dimensions
- Multidimensional Searching Problems
- Finding Minimum Spanning Trees
- Multidimensional divide-and-conquer