de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch

Hilfe Wegweiser Impressum Kontakt Einloggen

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Bericht

Randomized incremental construction of abstract Voronoi diagrams

MPG-Autoren

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

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)

MPI-I-93-105.pdf
(beliebiger Volltext), 17MB

Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

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

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.