On the Complexity of d-Dimensional Voronoi Diagrams.
Abstract
For n points p1,..., pn of Euclidean d-space E superscript d, the associated Voronoi diagram V(p1,...,pn) is a sequence (P1,...,Pn) of convex polyhedra covering E superscript d, where pi consists of all points of E superscript d that have pi as a nearest point in the set (p1,...,pn). Voronoi diagrams in E superscript 2 have been of interest because of their use by Shamos and others in providing efficient algorithms for a number of computational problems. The efficiency depends on the fact that the diagram itself can be computed efficiently (in time O(n log n) when d = 2). The present paper deals with the complexity of Voronoi diagrams based on n points of E superscript d.
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 01, 1979
- Accession Number
- ADA070098
Entities
People
- Victor Klee
Organizations
- University of Washington