Help Privacy Policy Disclaimer
  Advanced SearchBrowse





Randomized incremental construction of abstract Voronoi diagrams


Kučera,  Luděk
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)

(Any fulltext), 17MB

Supplementary Material (public)
There is no public supplementary material available

Kučera, L.(1993). Randomized incremental construction of abstract Voronoi diagrams (MPI-I-93-105). Saarbrücken: Max-Planck-Institut für Informatik.

Cite as: https://hdl.handle.net/11858/00-001M-0000-0014-B738-0
Abstract Voronoi diagrams were introduced by R.~Klein as an axiomatic basis of Voronoi diagrams. We show how to construct abstract Voronoi diagrams in time $O(n\log n)$ by a randomized algorithm, which is based on Clarkson and Shor's randomized incremental construction technique. The new algorithm has the following advantages over previous algorithms: \begin{itemize} \item It can handle a much wider class of abstract Voronoi diagrams than the algorithms presented in [Kle89b, MMO91]. \item It can be adapted to a concrete kind of Voronoi diagram by providing a single basic operation, namely the construction of a Voronoi diagram of five sites. Moreover, all geometric decisions are confined to the basic operation, and using this operation, abstract Voronoi diagrams can be constructed in a purely combinatorial manner.