Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen: doi:10.22028/D291-26122
Titel: On the construction of abstract Voronoi diagrams, II
Verfasser: Klein, Rolf
Mehlhorn, Kurt
Meiser, Stefan
Sprache: Englisch
Erscheinungsjahr: 1989
Quelle: Saarbrücken, 1989
Freie Schlagwörter: Voronoi diagrams
randomized algorithms
DDC-Sachgruppe: 004 Informatik
Dokumentart : Report (Bericht)
Kurzfassung: Abstract Voronoi Diagrams are defined by a system of bisecting curves in the plane, rather than by the concept of distance [K88a,b]. Mehlhorn, Meiser, Ó'Dúnlaing [MMO] showed how to construct such diagrams in time O(n log n) by a randomized algorithm if the bisecting curves are in general position. In this paper we drop the general position assumption. Moreover, we show that the only geometric operation in the algorithm is the construction of a Voronoi diagram for five sites. Using this operation, abstract Voronoi diagrams can be constructed in a purley combinatorial manner. This has the following advantages. On the one hand, the construction of a five-site-diagram is the only operation depending on the particular type of bisecting curves and we can therefore apply the algorithm to all concrete diagrams by simply replacing this operation. On the other hand, this is the only operation computing intersection points; thus, problems arising from instable numerical computations can occur only there.
Link zu diesem Datensatz: urn:nbn:de:bsz:291-scidok-41768
hdl:20.500.11880/26178
http://dx.doi.org/10.22028/D291-26122
Schriftenreihe: Technischer Bericht / A / Fachbereich Informatik, Universität des Saarlandes
Band: 1989/03
SciDok-Publikation: 5-Sep-2011
Fakultät: Fakultät 6 - Naturwissenschaftlich-Technische Fakultät I
Fachrichtung: MI - Informatik
Fakultät / Institution:MI - Fakultät für Mathematik und Informatik

Dateien zu dieser Ressource:
Datei Beschreibung GrößeFormat 
fb14_1989_03.pdf3,5 MBAdobe PDFÖffnen/Anzeigen


Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.