Abstract
Geometric closest-point problems deal with the proximity relationships in k-dimensional point sets. Examples of closest-point problems include building minimal spanning trees, nearest neighbor searching, and triangulation construction. M. I. Shamos and D. Hoey have shown how the Voronoi diagram can be used to solve a number of planar closest-point problems in optimal worst-case time. Their work is extended, in the form of 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 minimal spanning trees.
| Original language | English |
|---|---|
| Pages | 843-851 |
| Number of pages | 9 |
| State | Published - 1978 |
| Event | Proc Annu Allerton Conf Commun Control Comput 16th - Monticello, IL, USA Duration: 4 Oct 1978 → 6 Oct 1978 |
Conference
| Conference | Proc Annu Allerton Conf Commun Control Comput 16th |
|---|---|
| City | Monticello, IL, USA |
| Period | 4/10/78 → 6/10/78 |