Robert Sedgewick: Algorithmen

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


28. Probleme des nächsten Punktes



Voronoi-Diagramme

Die Menge alle Punkte, die von einem gegebenen Punkt in einer Punktmenge einen geringeren Abstand haben als von allen anderen Punkten in der Punktmenge, ist eine interessante geometrische Struktur, die als das Voronoi-Polygon für den Punkt bezeichnet wird. Die Vereinigung aller Voronoi-Polygone für eine Punktmenge wird ihr Voronoi-Diagramm genannt. Dies ist der Grundbaustein für Berechnungen zu Problemen des nächsten Punktes: Wir werden sehen, daß die meisten der von uns behandelten Probleme, in denen Abstände zwischen Punkten eine Rolle spielen, natürliche und interessante Lösungen besitzen, die auf dem Voronoi-Diagramm beruhen. Die Diagramme für unsere Beispiel-Punktmengen sind in Abbildung 28.4 dargestellt.

Abbildung 28.4
Abbildung 28.4 Voronoi-Diagramm.

Das Voronoi-Polygon für einen Punkt wird von den Mittelsenkrechten der Strecken gebildet, die den Punkt mit den ihm am nächsten liegenden Punkten verbinden. Seine tatsächliche Definition wird umgekehrt formuliert: Das Voronoi-Polygon ist definiert als die Randlinie der Menge aller Punkte in der Ebene, die näher bei dem gegebenen Punkt liegen als bei irgendeinem anderen Punkt in der Punktmenge, und jede Seite des Voronoi-Polygons trennt einen gegebenen Punkt von einem der ihm »nächstgelegenen« Punkte.

Die zum Voronoi-Diagramm duale Struktur, die in Abbildung 28.5 dargestellt ist, macht diese Entsprechung explizit deutlich: In der dualen Struktur werden von jedem Punkt zu allen Punkten, die ihm »am nächsten« liegen, Linien gezogen. Dies wird auch Delaunay-Triangulation genannt. Anders gesagt, x und y sind in der zum Voronoi-Diagramm dualen Struktur verbunden, wenn ihre Voronoi-Polygone eine Seite gemeinsam haben.

Abbildung 28.5
Abbildung 28.5 Delaunay-Triangulation.

Das Voronoi-Diagramm und die Delaunay-Triangulation haben viele Eigenschaften, die zu effizienten Algorithmen für Probleme des nächsten Punktes führen. Die Eigenschaft, die die Effizienz dieser Algorithmen gewährleistet, besteht darin, daß die Anzahl der Linien sowohl im Diagramm als auch in der dualen Struktur proportional zu einer kleinen Konstanten mal N ist. Zum Beispiel muß die Linie, die das nächste Paar von Punkten verbindet, in der dualen Struktur enthalten sein, so daß das Problem aus dem vorigen Abschnitt gelöst werden kann, indem die duale Struktur berechnet wird und dann einfach unter den Linien in der dualen Struktur die Linie mit der minimalen Länge bestimmt wird. Analog muß die Linie, die jeden Punkt mit seinem nächsten Nachbarn verbindet, in der dualen Struktur enthalten sein, so daß das Problem aller nächsten Nachbarn unmittelbar auf das Auffinden der dualen Struktur zurückgeführt werden kann. Die konvexe Hülle der Punktmenge ist ein Teil der dualen Struktur, so daß die Berechnung der zum Voronoi-Diagramm dualen Struktur einen weiteren Algorithmus zur Bestimmung der konvexen Hülle liefert. In Kapitel 31 betrachten wir noch ein anderes Beispiel eines Problems, welches effizient gelöst werden kann, indem zuerst die duale Struktur zum Voronoi-Diagramm ermittelt wird.

Die für die Definition verwendete Eigenschaft des Voronoi-Diagramms besagt, daß es benutzt werden kann, um das Problem des nächsten Nachbarn zu lösen: Um für einen gegebenen Punkt den nächsten Nachbarn in einer Punktmenge zu identifizieren, brauchen wir nur herauszufinden, in welchem Voronoi-Polygon sich der Punkt befindet. Es ist möglich, die Voronoi-Polygone in einer Struktur von der Art eines 2D-Baumes zu organisieren, um eine effiziente Durchführung dieser Suche zu ermöglichen.

Das Voronoi-Diagramm kann unter Verwendung eines Algorithmus berechnet werden, der die gleiche allgemeine Struktur hat wie der obige Algorithmus des nächsten Punktes. Die Punkte werden zuerst nach ihrer x-Koordinate sortiert. Danach wird diese Ordnung verwendet, um die Punktmenge in zwei Hälften zu zerlegen, was zu zwei rekursiven Aufrufen zur Bestimmung des Voronoi-Diagramms der Punktmenge für jede Hälfte führt. Gleichzeitig werden die Punkte nach y sortiert; schließlich werden die beiden Voronoi-Diagramme für die beiden Hälften gemischt. Wie zuvor kann bei diesem Mischen (das bei pass=2 vorgenommen wird) die Tatsache ausgenutzt werden, daß die Punkte vor den rekursiven Aufrufen nach x sortiert sind, und daß nach den rekursiven Aufrufen die Punkte nach y sortiert und die Voronoi-Diagramme für die beiden Hälften erzeugt worden sind. Jedoch ist das Mischen selbst mit diesen Hilfsmitteln eine sehr komplizierte Aufgabe, und die Darstellung einer vollständigen Implementation würde über den Rahmen dieses Buches hinausgehen.

Das Voronoi-Diagramm ist sicherlich die natürliche Struktur für Probleme des nächsten Punktes, und das Verstehen der Merkmale eines Problems anhand des Voronoi-Diagramms oder der zu ihm dualen Struktur ist gewiß eine lohnenswerte Übung. Für viele spezielle Probleme kann jedoch eine direkte, auf dem im vorliegenden Kapitel angegebenen allgemeinen Schema beruhende Implementation geeignet sein. Dieses Schema ist leistungsfähig genug, um das Voronoi-Diagramm zu berechnen; dabei ist es auch leistungsfähig genug für Algorithmen, die auf dem Voronoi-Diagramm beruhen, und es kann zu einfacheren, effizienteren Programmen führen, wie wir im Falle des Problems des nächsten Paares gesehen haben.


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