de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Report

Randomized incremental construction of abstract Voronoi diagrams

MPS-Authors

Kucera,  Ludek
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Locator
There are no locators available
Fulltext (public)

MPI-I-93-105.pdf
(Any fulltext), 17MB

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

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


Cite as: http://hdl.handle.net/11858/00-001M-0000-0014-B738-0
Abstract
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.