Higher-dimensional Voronoi diagrams in linear expected time (Q804320)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Higher-dimensional Voronoi diagrams in linear expected time |
scientific article |
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
