Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


25. Bestimmung der konvexen Hülle



Aspekte der Leistungsfähigkeit

Wie im vorangegangenen Kapitel erwähnt wurde, lassen sich geometrische Algorithmen schwerer analysieren als Algorithmen für manche der anderen Gebiete, die wir betrachtet haben, da die Eingabedaten (und Ausgabedaten) sich schwerer charakterisieren lassen. Oft ist es nicht sinnvoll, von »zufälligen« Punktmengen zu sprechen: Wenn zum Beispiel N groß wird, kommt die konvexe Hülle von Punkten, die gleichmäßig auf einem Rechteck verteilt sind, dem Rechteck, auf dem die Verteilung definiert ist, sehr nahe. Die Algorithmen, die wir betrachtet haben, hängen von verschiedenen Eigenschaften der Verteilung der Punktmenge ab und sind daher in der Praxis nicht vergleichbar, da ihr analytischer Vergleich ein Verständnis von sehr komplizierten Wechselwirkungen zwischen wenig erforschten Eigenschaften von Punktmengen erfordern würde. Andererseits können wir einiges über die Leistungsfähigkeit der Algorithmen aussagen, was die Auswahl eines Algorithmus für eine spezielle Anwendung erleichtert.

Eigenschaft 25.1 Nach dem Sortieren ist das Durchsuchen nach Graham ein in linearer Zeit ablaufender Prozeß.

Man muß etwas nachdenken, um sich davon zu überzeugen, daß dies zutrifft, da in dem Programm eine geschachtelte Schleife auftritt. Es ist jedoch leicht einzusehen, daß kein Punkt mehr als einmal »eliminiert« wird, so daß der Programmabschnitt innerhalb dieser doppelten Schleife weniger als N mal durchlaufen wird. Die Gesamtzeit, die bei Anwendung dieser Methode für die Bestimmung der konvexen Hülle benötigt wird, ist O(N log N), doch die »innere Schleife« der Methode ist das Sortieren selbst, dessen Effizienz unter Benutzung der Techniken aus den Kapiteln 8 - 12 erhöht werden kann. w.z.b.w.

Eigenschaft 25.2 Wenn der Hülle M Ecken angehören, erfordert die Einwickel-Methode ungefähr MN Schritte.

Zuerst müssen wir N - 1 Winkel berechnen, um das Minimum zu finden, dann N - 2, um das nächste zu finden, dann N - 3 usw., so daß die Anzahl der Winkelberechnungen (N - 1)+(N - 2)+...+(N - M + 1) ist, was genau (M - 1)N - M(M - 1)/2 ergibt. Um dies analytisch mit dem Durchsuchen nach Graham zu vergleichen, wäre es erforderlich, eine Formel zu finden, die M über N ausdrückt, was in der stochastischen Geometrie ein kompliziertes Problem ist. Für eine Gleichverteilung auf einem Kreis (und einige andere) lautet die Antwort, daß M O(N1/3) ist, und für nicht zu große Werte von N ist N1/3 mit log N vergleichbar (was der zu erwartende Wert für eine Gleichverteilung auf einem Rechteck ist), so daß für dieses Verfahren der Vergleich mit dem Durchsuchen nach Graham sehr günstig ausfällt. Natürlich sollte der ungünstigste Fall N2 nie vergessen werden. w.z.b.w.

Eigenschaft 25.3 Die Methode der inneren Elimination ist im durchschnittlichen Fall linear.

Eine vollständige mathematische Analyse dieses Verfahrens würde sogar noch kompliziertere Untersuchungen mit Hilfe der stochastischen Geometrie erfordern als oben, doch das prinzipielle Ergebnis stimmt mit dem überein, was die Intuition erwarten läßt: Fast alle Punkte entfallen auf das Innere des Vierecks und werden ausgesondert; die Anzahl der verbleibenden Punkte ist O(sqrtN). Dies gilt sogar dann, wenn das oben beschriebene Rechteck benutzt wird. Dies führt dazu, daß die durchschnittliche Laufzeit des gesamten Algorithmus zur Bestimmung der konvexen Hülle proportional zu N ist, da die meisten Punkte nur einmal betrachtet werden (wenn sie ausgesondert werden). Im durchschnittlichen Fall spielt es keine große Rolle, welches Verfahren anschließend angewandt wird, da nur wenige Punkte übrigbleiben. Um jedoch Vorkehrungen für den ungünstigsten Fall (wenn alle Punkte auf der Hülle liegen) zu treffen, ist es ratsam, das Durchsuchen nach Graham zu benutzen. Das ergibt einen Algorithmus, der in der Praxis meist in linearer Zeit, im schlimmsten Fall jedoch garantiert in einer zu N log N proportionalen Zeit abläuft. sqrt

Das als Eigenschaft 25.3 formulierte Ergebnis für den durchschnittlichen Fall gilt nur für zufällig verteilte Punkte in einem Rechteck, und im ungünstigsten Fall wird mit der Methode der inneren Elimination gar nichts eliminiert. Trotzdem ist das Verfahren auch für andere Verteilungen oder für Punktmengen mit unbekannten Eigenschaften zu empfehlen, da die Kosten niedrig sind (ein lineares Durchsuchen der Punkte, mit wenigen einfachen Tests) und die möglichen Einsparungen groß sind (die meisten Punkte können leicht eliminiert werden). Das Verfahren läßt sich auch auf den Fall höherer Dimensionen verallgemeinern.

Es ist möglich, eine rekursive Variante des Verfahrens der inneren Elimination zu entwickeln: Bestimme Extrempunkte und entferne Punkte aus dem Inneren des durch sie definierten Vierecks wie oben, betrachte jedoch dann die verbleibenden Punkte als in Teilprobleme zerlegt, die unter Anwendung des gleichen Verfahrens unabhängig voneinander gelöst werden können. Diese rekursive Technik ist mit der zu Quicksort ähnlichen Prozedur select für die Auswahl vergleichbar, die im Kapitel 12 behandelt wurde. Wie diese Prozedur besitzt sie den Nachteil, daß im ungünstigsten Fall eine zu N2 proportionale Laufzeit auftreten kann. Wenn zum Beispiel alle ursprünglichen Punkte der konvexen Hülle angehören, werden beim rekursiven Schritt keine Punkte ausgesondert. Wie bei select ist die Laufzeit im durchschnittlichen Fall linear (obwohl es nicht einfach ist, dies zu beweisen). Da jedoch so viele Punkte im ersten Schritt eliminiert werden, dürfte sich bei praktischen Anwendungen der Aufwand nicht lohnen, der erforderlich ist, um eine weitere rekursive Zerlegung vorzunehmen.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]