SciDok

Eingang zum Volltext in SciDok

Hinweis zum Urheberrecht

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


Berechnung konvexer Hüllen in erwarteter Linearzeit

Son, Jung-Bae

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

Bookmark bei Connotea Bookmark bei del.icio.us
SWD-Schlagwörter: Technische Informatik
Institut: Fachrichtung 6.2 - Informatik
DDC-Sachgruppe: Informatik
Dokumentart: Report (Bericht)
Schriftenreihe: Technischer Bericht / A / Fachbereich Informatik, Universität des Saarlandes
Bandnummer: 1999/04
Sprache: Deutsch
Erstellungsjahr: 1998
Publikationsdatum: 22.06.2005
Kurzfassung auf Deutsch: In dieser Arbeit wird ein Reduktions-Algorithmus zur Berechnung der konvexen Hülle einer Punktmenge im reellen, d-dimensionalen, euklidischen Raum angeben und seine erwartete Laufzeit ermittelt. Der Algorithmus geht folgendermaBen vor: Zunächst wird in einem Aussiebschritt die Anzahl der Eingabepunkte reduziert. Von den übriggebliebenen Punkten wird anschließend mit einem Algorithmus der worst-case Laufzeit O(n log n) im R^d, d < 3 und O(n^lfloorfracd2rfloor+1) im R^d, d > 3, die konvexe Hülle berechnet. Das Aussiebverfahren ist derart, daß die konvexe Hülle der übriggebliebenen Punkte mit der konvexen Hülle der Eingabepunkte übereinstimmt. Bei Gleichverteilung auf einem d-dimensionalen Hyperquader beträgt die erwartete Laufzeit des Verfahrens O(n). Liegt eine Wahrscheinlichkeitsdichte f : R^d rightarrow R vor, bei der für alle x in R^d der Funktionswert f(x) > 0 ist, z.B. die Dichte der d-dimensionalen Standard-Normalverteilung, dann betragen die erwarteten Kosten ebenfalls O(n). Bei bestimmten rotationssymmetrischen Dichten im R^d läßt sich die konvexe Hülle ebenfalls asymptotisch in erwarteter Linearzeit berechnen. Ist d geq 4, so berechnet das Verfahren für bestimmte komponenten-unabhängige Dichten eine Obermenge der konvexen Hülle asymptotisch in linearer erwarteter Laufzeit. Bei Dichten f : R^d rightarrow R, deren gesamte Wahrscheinlichkeitsmaße in einem hyperquaderförmigen Gebiet H versammelt ist, so daß [ int^_R^d f(x)dx = int_H f(x)dx = 1 ] und f(x) > 0 für alle x in H ist, liegt die erwartete Laufzeit mit O(n) + o(n log n) für d lt 3 und O(n) + o(n^lfloorfracd2rfloor) -- wenn man einen worst-case O(n^lfloorfracd2rfloor) statt O(n^lfloorfracd2rfloor + 1) Algorithmus benutzt -- für d > 3 deutlich unter der worst-case Laufzeit gängiger Algorithmen. zur Berechnung konvexer Hüllen.

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