Robert Sedgewick: Algorithmen

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


25. Bestimmung der konvexen Hülle



Innere Elimination

Nahezu jedes Verfahren zur Bestimmung der konvexen Hülle kann mit Hilfe einer einfachen Methode, die die meisten Punkte schnell aussondert, beträchtlich verbessert werden. Die Grundidee ist einfach: Wähle vier Punkte aus, von denen bekannt ist, daß sie der Hülle angehören, und entferne dann alles, was sich innerhalb des durch diese vier Punkte gebildeten Vierecks befindet. Als Ergebnis bleiben viel weniger Punkte übrig, die zum Beispiel mittels Durchsuchens nach Graham oder mit Hilfe der Einwickel-Methode betrachtet werden müssen.

Die vier Punkte, von denen bekannt ist, daß sie der Hülle angehören, sollten unter Beachtung sämtlicher verfügbarer Informationen über die eingegebenen Punkte ausgewählt werden. Allgemein gilt, daß es am besten ist, die Wahl der Punkte an die Verteilung der Eingabedaten anzupassen. Wenn zum Beispiel alle Werte von x und y innerhalb gewisser Bereiche gleich wahrscheinlich sind (eine Gleichverteilung in einem Rechteck), dann lassen sich nahezu alle Punkte entfernen, wenn die vier Punkte möglichst in den Ecken gewählt werden. Abbildung 25.7 zeigt, daß diese Methode in unseren beiden Beispielen von Punktmengen die meisten nicht der Hülle angehörenden Punkte beseitigt.

Abbildung 25.7
Abbildung 25.7 Innere Elimination.

Bei einer Implementation des Verfahrens der inneren Elimination ist die »innere Schleife« für zufällige Punktmengen der Test, ob ein gegebener Punkt in das Test-Viereck fällt oder nicht. Dieser kann etwas beschleunigt werden, indem ein Rechteck verwendet wird, dessen Seiten parallel zur x- bzw. y-Achse sind. Das größte derartige Rechteck, das sich innerhalb des oben beschriebenen Vierecks befindet, läßt sich aus den Koordinaten der Eckpunkte dieses Vierecks leicht bestimmen. Die Verwendung dieses Rechtecks bewirkt die Elimination von weniger Punkten aus dem Inneren, doch die Geschwindigkeit des Tests gleicht diesen Verlust bei weitem aus.


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