Eingang zum Volltext in SciDok
Lizenz
Report (Bericht) zugänglich unter
On the construction of abstract Voronoi diagrams
URN: urn:nbn:de:bsz:291-scidok-41734
URL: http://scidok.sulb.uni-saarland.de/volltexte/2011/4173/
pdf-Format:
Dokument 1.pdf (3.170 KB)
Freie Schlagwörter (Englisch):
Voronoi diagrams , randomized algorithms
Institut:
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