Higher-dimensional Voronoi diagrams in linear expected time (Q804320)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Higher-dimensional Voronoi diagrams in linear expected time |
scientific article; zbMATH DE number 4201702
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Higher-dimensional Voronoi diagrams in linear expected time |
scientific article; zbMATH DE number 4201702 |
Statements
Higher-dimensional Voronoi diagrams in linear expected time (English)
0 references
1991
0 references
The author developed a general method which is applied for bounding the expected combinatorial complexity (of order \(\Theta\) (n)) of Voronoi diagrams on n independent and identically distributed points in higher- dimensional Euclidean spaces. The optimal bucket algorithm (with the floor function in the instruction repertoire) is designed and analyzed. The paper is well-written.
0 references
randomized algorithm
0 references
expected combinatorial complexity
0 references
Voronoi diagrams
0 references
