Accession Number:
ADA070098
Title:
On the Complexity of d-Dimensional Voronoi Diagrams.
Descriptive Note:
Technical rept.,
Corporate Author:
WASHINGTON UNIV SEATTLE DEPT OF MATHEMATICS
Personal Author(s):
Report Date:
1979-03-01
Pagination or Media Count:
13.0
Abstract:
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.
Descriptors:
Subject Categories:
- Numerical Mathematics