Robert Sedgewick: Algorithmen

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


25. Bestimmung der konvexen Hülle



Spielregeln

Die Eingabe für einen Algorithmus zur Bestimmung der konvexen Hülle erfolgt natürlich in Form eines Felds von Punkten; wir können sonst den im vorangegangenen Kapitel definierten Typ point verwenden. Ausgegeben wird ein Polygon, das ebenfalls als ein Feld von Punkten dargestellt wird; dieses hat die Eigenschaft, daß man, wenn man die Punkte in der Reihenfolge, in der sie im Feld erscheinen, verbindet, den Umriß des Polygons erhält. Es könnte scheinen, daß dies eine zusätzliche Ordnungsbedingung für die Berechnung der konvexen Hülle erfordert (warum sollten die Punkte der Hülle nicht einfach in beliebiger Reihenfolge zurückgegeben werden?), doch zum einen ist eine Ausgabe in der geordneten Form offenbar von größerem Nutzen, und zum anderen ist gezeigt worden, daß die ungeordnete Berechnung nicht leichter zu realisieren ist. Für alle Algorithmen, die wir betrachten, ist es zweckmäßig, die Berechnung an Ort und Stelle vorzunehmen: Das Feld, das für die ursprüngliche Punktmenge verwendet wurde, wird auch für die Speicherung der Ausgabedaten benutzt. Die Algorithmen ordnen einfach die Punkte im ursprünglichen Feld so um, daß die konvexe Hülle in den ersten M Positionen in geordneter Folge erscheint.

Aus der obigen Beschreibung geht hervor, daß die Berechnung der konvexen Hülle in enger Beziehung zum Sortieren steht. Tatsächlich kann ein Algorithmus zur Berechnung der konvexen Hülle folgendermaßen zum Sortieren verwendet werden: Wenn N zu sortierende Zahlen gegeben sind, wandle man sie in (durch ihre Polarkoordinaten gegebene) Punkte um, indem man die Zahlen als (in geeigneter Weise normierte) Winkel mit einem festen Radius behandelt. Die konvexe Hülle dieser Punktmenge ist ein N-Eck, das sämtliche Punkte enthält. Da nun die Ausgabedaten in der Reihenfolge geordnet werden müssen, in der die Punkte in diesem Polygon angeordnet sind, können sie verwendet werden, um die sortierte Folge der ursprünglichen Werte zu erhalten (wir erinnern daran, daß die Eingabedaten ungeordnet waren). Dies ist kein formaler Beweis dafür, daß die Berechnung der konvexen Hülle nicht einfacher ist als Sortieren, da zum Beispiel die Kosten der trigonometrischen Funktionen berücksichtigt werden müssen, die benötigt werden, um die Zahlen in Eckpunkte des Polygons umzuwandeln. Der Vergleich von Algorithmen für die konvexe Hülle (die trigonometrische Operationen erfordern) mit Sortieralgorithmen (die Vergleiche zwischen Schlüsseln erfordern) ähnelt in gewisser Hinsicht einem Vergleich zwischen Äpfeln und Birnen; nichtsdestotrotz wurde nachgewiesen, daß jeder beliebige Algorithmus für die konvexe Hülle ungefähr N log N Operationen erfordern muß, ebenso viele wie zum Sortieren (obwohl die Operationen wahrscheinlich sehr unterschiedlich sind). Es ist zweckmäßig, die Bestimmung der konvexen Hülle einer Punktmenge als eine Art »zweidimensionales Sortieren« zu betrachten, da bei der Untersuchung von Algorithmen zur Bestimmung der konvexen Hülle häufig Parallelen zu Sortieralgorithmen auftreten.

Tatsächlich zeigen die von uns behandelten Algorithmen, daß die Bestimmung der konvexen Hülle auch nicht aufwendiger ist als Sortieren: Es gibt verschiedene Algorithmen, die in einer Zeit ablaufen, die im ungünstigsten Fall proportional zu N log N ist. Viele der Algorithmen tendieren dazu, bei realen Punktmengen sogar noch weniger Zeit aufzuwenden, da ihre Laufzeit davon abhängig ist, wie die Punkte verteilt sind und wie viele Punkte zur Hülle gehören.

Wie bei allen geometrischen Algorithmen müssen wir entarteten Fällen, die bei der Eingabe auftreten könnten, eine gewisse Beachtung schenken. Was ist zum Beispiel die konvexe Hülle einer Punktmenge, die alle auf derselben Strecke liegen? Je nach Anwendungsfall könnten dies alle Punkte sein, oder nur die zwei Endpunkte, oder vielleicht wäre eine beliebige Menge, die die beiden Endpunkte enthält, eine Lösung. Obwohl dies ein extremes Beispiel zu sein scheint, ist es nicht ungewöhnlich, wenn mehr als zwei Punkte auf einem der Geradenabschnitte liegen, die die Hülle einer Menge von Punkten definieren. In den nachfolgend betrachteten Algorithmen bestehen wir nicht darauf, daß Punkte, die auf einer Seite des Polygons liegen, mit aufgenommen werden, da dies im allgemeinen mehr Aufwand erfordert (obwohl wir an geeigneter Stelle darauf hinweisen werden, wie dies realisiert werden könnte). Andererseits bestehen wir auch nicht darauf, diese Punkte wegzulassen, da diese Bedingung bei Bedarf nachträglich überprüft werden kann.


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