SciDok

Eingang zum Volltext in SciDok

Lizenz

Report (Bericht) zugänglich unter
URN: urn:nbn:de:bsz:291-scidok-41734
URL: http://scidok.sulb.uni-saarland.de/volltexte/2011/4173/


On the construction of abstract Voronoi diagrams

Mehlhorn, Kurt ; Meiser, Stefan ; Ó'Dúnlaing, C.

pdf-Format:
Dokument 1.pdf (3.170 KB)

Bookmark bei Connotea Bookmark bei del.icio.us
Freie Schlagwörter (Englisch): Voronoi diagrams , randomized algorithms
Institut: Fachrichtung 6.2 - Informatik
DDC-Sachgruppe: Informatik
Dokumentart: Report (Bericht)
Schriftenreihe: Technischer Bericht / A / Fachbereich Informatik, Universität des Saarlandes
Bandnummer: 1989/01
Sprache: Englisch
Erstellungsjahr: 1989
Publikationsdatum: 05.09.2011
Kurzfassung auf Englisch: 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].
Lizenz: Standard-Veröffentlichungsvertrag

Home | Impressum | Über SciDok | Policy | Kontakt | Datenschutzerklärung | English