Berechnung konvexer Hüllen in erwarteter Linearzeit

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.