Randomisiert Inkrementelle Konstruktion der konvexen Hülle =========================================== Wolfgang Mulzer Sei P = {p1, p2, ... pn} eine Menge von n Punkten in der Ebene, in allgemeiner Lage. Gesucht ist CH(P), die konvexe Hülle von P. Fuer i = 3, ..., n, sei Pi := {p1, p2, ..., pi}. Der inkrementelle Algorithmus berechnet sukzessive CH(P3), CH(P4), ..., CH(Pn). Dabei wird jeweils CH(Pi) durch Einfügen des Punktes pi in die Huelle CH(P(i-1)) berechnet. 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 Kante e von CH(Pi), so dass p links von der Geraden durch e liegt. Die Kante e muss beim Einfuegen von p geloescht werden und heisst deswegen eine Konfliktkante von e. Fuer jede Kante e in E(CH(Pi)) gibt es eine Konfliktliste Ce, die alle Punkte p in P \ Pi mit Cp = e enthält. Zu Beginn lassen sich CH(P3) und die Konfliktinformationen leicht berechnen. Nun benutzen wir die Konfliktinformation, um pi in CH(P(i-1)) einzufügen. Wenn Cp = NULL ist, so liegt pi in CH(P(i-1)), und wir müssen nichts tun. Ansonsten wissen wir, dass die Kante e = Cp gelöscht werden muss. Wir laufen von e in beide Richtungen an CH(P(i-1)) entlang, bis wir zu jeweils ersten Kante gelangen, mit der pi nicht mehr im Konflikt steht. Die Punkte q1 und q2, welche die Konfliktregion von pi begrenzen, sind die Tangentialpunkte für pi. In CH(Pi) gibt es zwei neue Kanten e1 und e2 von pi zu q1 und q2, und alle Kanten in der Konfliktregion werden gelöscht. Jetzt müssen wir noch die Konfliktinformationen aktualisieren. Dazu betrachten wir für jede zu löschende Kante e' die Konfliktliste C(e'), und für jeden Punkt q in dieser Liste C(e') tun wir folgendes: Wir laufen wie bei pi von e' in beide Richtungen an den Konfliktkanten für q entlang. Hierbei laufen wir aber nur so lange, wie die aktuelle Kante auch im Konflikt mit pi steht (also gelöscht werden muss). Dadurch gelangen wir zu dem Tangentialpunkt q1, dem Tangentialpunkt q2, zu beiden Tangentialpunkten, oder zu keinem Tangentialpunkt. Für jeden Tangentialpunkt, den wir so entdecken, testen wir, ob q im Konflikt mit der entsprechenden Kante steht. Wenn ja, aktualisieren wir den Konfliktzeiger Cq und die Konfliktliste für die entsprechende Tangentialkante. Dadurch werden alle Konfliktzeiger und Konfliktlisten aktualisiert. Zum Abschluss löschen wir alle Kanten im Konflikt mit pi. Dieser Vorgang wiederholt sich, bis CH(Pn) = CH(P) gefunden wurde. Laufzeitanalyse: Strukturelle Anderung. In jedem Schritt werden höchstens zwei Kanten erzeugt. Jede erzeugte Kante wird höchstens einmal gelöscht, also werden im Laufe des Algorithmus höchstens 2n Kanten erzeugt und höchstens 2n Kanten gelöscht. Konfliktänderung. Beim Aktualisieren der Konfliktinformation wird jede Kante 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 Kanten und Punkten in P bestehen. Im schlimmsten Fall ist diese Zahl quadratisch.