Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen: doi:10.22028/D291-25793
Titel: Berechnung konvexer Hüllen in erwarteter Linearzeit
Verfasser: Son, Jung-Bae
Sprache: Deutsch
Erscheinungsjahr: 1998
SWD-Schlagwörter: Technische Informatik
DDC-Sachgruppe: 004 Informatik
Dokumentart : Report (Bericht)
Kurzfassung: 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.
Link zu diesem Datensatz: urn:nbn:de:bsz:291-scidok-3485
hdl:20.500.11880/25849
http://dx.doi.org/10.22028/D291-25793
Schriftenreihe: Technischer Bericht / A / Fachbereich Informatik, Universität des Saarlandes
Band: 1999/04
SciDok-Publikation: 22-Jun-2005
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-99-04.pdf910,81 kBAdobe PDFÖffnen/Anzeigen


Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.