Optimal Expected-Time Algorithms for Closest-Point Problems
Abstract
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 01, 1979
- Accession Number
- ADA066740
Entities
People
- Andrew C. Yao
- Bruce W. Weide
- John Louis Bentley
Organizations
- Carnegie Mellon University