Robert Sedgewick: Algorithmen

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


25. Bestimmung der konvexen Hülle



Wenn wir eine große Anzahl von Punkten zu verarbeiten haben, interessieren uns oft die äußeren Grenzen der Punktmenge. Wer eine Darstellung einer in der Ebene gezeichneten Menge von Punkten betrachtet, hat wenig Mühe, die im »Inneren« der Punktmenge gelegenen Punkte von den am Rande gelegenen zu unterscheiden. Diese Unterscheidung ist eine grundlegende Eigenschaft von Punktmengen; in diesem Kapitel werden wir sehen, wie sie exakt charakterisiert werden kann, indem wir Algorithmen betrachten, die der Hervorhebung der »natürlichen Grenzpunkte« dienen.

Die mathematische Methode zur Beschreibung der natürlichen Grenze einer Menge von Punkten beruht auf einer geometrischen Eigenschaft, die Konvexität genannt wird. Dies ist ein einfacher Begriff, der dem Leser vielleicht schon früher begegnet ist: Ein konvexes Polygon hat die Eigenschaft, daß jede Linie, die zwei beliebige innerhalb des Polygons gelegene Punkte verbindet, selbst vollständig innerhalb des Polygons liegen muß. Zum Beispiel ist das »einfache abgeschlossene Polygon«, das wir im vorangegangenen Kapitel berechnet haben, sicherlich nicht konvex; andererseits ist jedes Dreieck oder Rechteck konvex.

Die mathematische Bezeichnung für die natürliche Grenze einer Punktmenge lautet konvexe Hülle. Die konvexe Hülle einer Menge von Punkten in der Ebene ist als das kleinste konvexe Polygon definiert, das alle diese Punkte enthält. Hierzu äquivalent ist die Definition, daß die konvexe Hülle der kürzeste Pfad ist, der die Punkte umschließt. Es ist eine offensichtliche, leicht beweisbare Eigenschaft der konvexen Hülle, daß die Ecken des die Hülle definierenden konvexen Polygons Punkte aus der ursprünglichen Punktmenge sind. Wenn N Punkte gegeben sind, so bilden einige von ihnen ein konvexes Polygon, in dem alle übrigen enthalten sind. Das Problem besteht darin, diese Punkte zu finden. Für die Bestimmung der konvexen Hülle sind viele Algorithmen entwickelt worden; wir wollen in diesem Kapitel einige der wichtigeren betrachten.

Abbildung 25.1 zeigt unsere Beispiele von Punktmengen aus Abbildung 24.1 und ihre konvexen Hüllen. Der Hülle der kleinen Menge gehören 8 Punkte an, der Hülle der größeren Menge 15 Punkte. Es ist möglich, daß die konvexe Hülle nur drei Punkte enthält (falls die drei Punkte ein großes Dreieck bilden, das alle anderen enthält), oder auch, daß ihr alle Punkte angehören (wenn die Punkte auf einem konvexen Polygon liegen, so bilden sie ihre eigene konvexe Hülle). Die Anzahl der Punkte für die konvexe Hülle einer »zufälligen« Punktmenge liegt irgendwo zwischen diesen Extremfällen, wie wir weiter unten sehen werden. Einige Algorithmen sind effizient, wenn der konvexen Hülle viele Punkte angehören; andere laufen besser ab, wenn ihr nur wenige angehören.

Abbildung 25.1
Abbildung 25.1 Konvexe Hüllen der Punkte aus Abbildung 24.1.

Eine grundlegende Eigenschaft der konvexen Hülle ist, daß eine beliebige außerhalb der Hülle verlaufende Gerade, wenn sie in irgendeiner Richtung zur Hülle hin verschoben wird, diese in einem ihrer Eckpunkte berührt. (Dies ist eine weitere Möglichkeit, die Hülle zu definieren: Es ist die Teilmenge der Punktmenge, die diejenigen Punkte enthält, die von einer aus dem Unendlichen unter einem beliebigen Winkel sich nähernden Geraden berührt werden können.) Insbesondere ist es leicht, einige Punkte zu finden, die garantiert der Hülle angehören, nämlich indem man diese Regel auf waagerechte und senkrechte Geraden anwendet: Die Punkte mit den kleinsten und größten Koordinaten x und y gehören alle der konvexen Hülle an. Diese Tatsache wird als Ausgangspunkt für die Algorithmen benutzt, die wir betrachten wollen.


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