Randomisiert Inkrementelle Konstruktion der konvexen Huelle im Raum =========================================== Wolfgang Mulzer Sei P = {p1, p2, ..., pn} eine Menge von n Punkten in im Raum, in allgemeiner Lage (d.h., keine vier Punkte von P liegen auf einer gemeinsamen Ebene). Gesucht ist CH(P), die konvexe Hülle von P. Fuer i = 4, ..., n, sei Pi := {p1, p2, ..., pi}. Der inkrementelle Algorithmus berechnet sukzessive CH(P4), CH(P5), ..., CH(Pn). Dabei wird jeweils CH(Pi) durch Einfuegen des Punktes pi in die Huelle CH(P(i-1)) berechnet. Die jeweilige konvexe Huelle wird repräsentiert durch eine DCEL, die den planaren Graphen G(CH(Pi)) repräsentiert. Um dieses Einfügen zu erleichtern, speichert der Algorithmus sogenannte Konfliktinformationen: Fuer jeden Punkt p in P \ Pi gibt es einen Zeiger Cp auf eine Facette f von CH(Pi), so dass p links von der Ebene durch f liegt. Die Facette f muss beim Einfuegen von p geloescht werden und heisst deswegen eine Konfliktfacette von p. Fuer jede Facette f von CH(Pi) gibt es eine Konfliktliste Cf, die alle Punkte p in P \ Pi mit Cp = f enthält. Zu Beginn lassen sich CH(P4) und die Konfliktinformationen leicht berechnen. Nun benutzen wir die Konfliktinformation, um pi in CH(P(i-1)) einzufügen. Wenn C(pi) = NULL ist, so liegt pi in CH(P(i-1)), und wir müssen nichts tun. Ansonsten wissen wir, dass die Facette f = C(p_i) gelöscht werden muss. Wir führen von f aus eine Breitennsuche im Dualgraphen von G(CH(P(i-1))) aus. Dabei besuchen wir aber nur Facetten von G(CH(P(i-1)), welche im Konflikt mit pi stehen. Das heisst, wir fügen eine noch nicht besuchte Facette f' nur dann in die BFS-Warteschlange ein, wenn pi links von der Ebene durch f' liegt. Die Konfliktregion von pi wird begrenzt durch einen einfachen Kreis in G(CH(P(i-1))). Diesen Kreis nennen wir Zi. In CH(Pi) gibt es neue Facetten von pi zu jeder Kante von Zi, und alle Facetten in der Konfliktregion werden gelöscht. Jetzt müssen wir noch die Konfliktinformationen aktualisieren. Dazu betrachten wir für jede zu löschende Facette f' die Konfliktliste C(f'), und für jeden Punkt q in dieser Liste C(f') tun wir folgendes: Wir führen wie bei pi von f' aus eine BFS in der Konfliktregion für q aus. Hierbei laufen wir aber nur so lange, wie die aktuelle Facette auch im Konflikt mit pi steht (also gelöscht werden muss). Dadurch erreichen wir alle Kanten von Zi, die zu einer Facette inzident sind, die im Konflikt mit q und pi steht. Für jede solche Kante von Zi testen wir, ob q im Konflikt mit der angrenzenden neu erzeugten Facette steht. Wenn ja, aktualisieren wir den Konfliktzeiger Cq und die Konfliktliste für die entsprechende neue Facette. Dadurch werden alle Konfliktzeiger und Konfliktlisten aktualisiert. Dieser Vorgang wiederholt sich, bis CH(Pn) = CH(P) gefunden wurde. Laufzeitanalyse: Strukturelle Änderung. Jede erzeugte Facette wird höchstens einmal gelöscht, also genügt es, die Anzahl der erzeugten Facetten abzuschätzen. Leider kann diese im schlimmsten Fall quadratisch sein. Mit Hilfe von Rueckwaertsanalyse kann man aber zeigen, dass die erwartete strukturelle Änderung linear ist (->VL). Konfliktänderung. Beim Aktualisieren der Konfliktinformation wird Facette höchstens einmal durchlaufen für jeden Punkt, der mit ihr im Konflikt steht. Also ist die Gesamtlaufzeit für die Konflitänderung proportional zur Gesamtanzahl der Konflikte, die zwischen erzeugten Facetten und Punkten in P bestehen. Durch einen analogen Beweis wie für den zweidimensionalen Fall kann man zeigen, dass die erwartete Anzahl dieser Konflikte O(n log n) ist. Dazu benötigt man eine dreidimensionale Version des Satzes von Clarkson, welcher besagt, dass die Anzahl der orientieren Ebenen, die von drei Punkten aus P aufgespannt werden und höchstens k Punkte aus P auf der linken Seite haben, höchstens O(nk^2) ist.