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.

Subject Categories:

  • Numerical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE