Please use this identifier to cite or link to this item:
doi:10.22028/D291-25793
Title: | Berechnung konvexer Hüllen in erwarteter Linearzeit |
Author(s): | Son, Jung-Bae |
Language: | German |
Year of Publication: | 1998 |
SWD key words: | Technische Informatik |
DDC notations: | 004 Computer science, internet |
Publikation type: | Report |
Abstract: | 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 to this record: | urn:nbn:de:bsz:291-scidok-3485 hdl:20.500.11880/25849 http://dx.doi.org/10.22028/D291-25793 |
Series name: | Technischer Bericht / A / Fachbereich Informatik, Universität des Saarlandes |
Series volume: | 1999/04 |
Date of registration: | 22-Jun-2005 |
Faculty: | MI - Fakultät für Mathematik und Informatik |
Department: | MI - Informatik |
Collections: | SciDok - Der Wissenschaftsserver der Universität des Saarlandes |
Files for this record:
File | Description | Size | Format | |
---|---|---|---|---|
fb14-99-04.pdf | 910,81 kB | Adobe PDF | View/Open |
Items in SciDok are protected by copyright, with all rights reserved, unless otherwise indicated.