Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen: doi:10.22028/D291-26121
Titel: On the construction of abstract Voronoi diagrams
Verfasser: Mehlhorn, Kurt
Meiser, Stefan
Ó'Dúnlaing, C.
Sprache: Englisch
Erscheinungsjahr: 1989
Freie Schlagwörter: Voronoi diagrams
randomized algorithms
DDC-Sachgruppe: 004 Informatik
Dokumentart : Report (Bericht)
Kurzfassung: We show that the abstract Voronoi diagram of n sites in the plane can be constructed in time O(n log n) by a randomized algorithm. This yields an alternative, but simpler, O(n log n) algorithm in many previously considered cases and the first O(n log n) algorithm in some cases, e.g., disjoint convex sites with the Euclidean distance function. Abstract Voronoi diagrams are given by a family of bisecting curves and were recently introduced by Klein [Kl88a]. Our algorithm is based on Clarkson and Shor's randomized incremental construction technique [CS].
Link zu diesem Datensatz: urn:nbn:de:bsz:291-scidok-41734
hdl:20.500.11880/26177
http://dx.doi.org/10.22028/D291-26121
Schriftenreihe: Technischer Bericht / A / Fachbereich Informatik, Universität des Saarlandes
Band: 1989/01
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_01.pdf3,17 MBAdobe PDFÖffnen/Anzeigen


Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.