Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen:
doi:10.22028/D291-26121
Titel: | On the construction of abstract Voronoi diagrams |
VerfasserIn: | Mehlhorn, Kurt Meiser, Stefan Ó'Dúnlaing, C. |
Sprache: | Englisch |
Erscheinungsjahr: | 1989 |
Freie Schlagwörter: | Voronoi diagrams randomized algorithms |
DDC-Sachgruppe: | 004 Informatik |
Dokumenttyp: | Forschungsbericht (Report zu Forschungsprojekten) |
Abstract: | 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 |
Datum des Eintrags: | 5-Sep-2011 |
Fakultät: | MI - Fakultät für Mathematik und Informatik |
Fachrichtung: | MI - Informatik |
Sammlung: | SciDok - Der Wissenschaftsserver der Universität des Saarlandes |
Dateien zu diesem Datensatz:
Datei | Beschreibung | Größe | Format | |
---|---|---|---|---|
fb14_1989_01.pdf | 3,17 MB | Adobe PDF | Öffnen/Anzeigen |
Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.