On the Complexity of d-Dimensional Voronoi Diagrams.
WASHINGTON UNIV SEATTLE DEPT OF MATHEMATICS
Pagination or Media Count:
For n points p1,..., pn of Euclidean d-space E superscript d, the associated Voronoi diagram Vp1,...,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 On log n when d 2. The present paper deals with the complexity of Voronoi diagrams based on n points of E superscript d.
- Numerical Mathematics