Gewichtete Farthest Color Voronoi Diagramme auf Bäumen und Graphen


Gegeben ist ein ungerichterter Graph und eine Menge von n Sites, die jeweil an einer bestimmten Position auf einer Kante des Graphens legen. Nehme an das jede dieser n Sites eine von k verschiedenen Typen von Einrichtungen repräsentiert, z.B. Schulen, Einkaufszentren, Krankenhäuser, usw. Eine Person sucht nun einen Ort zum Niederlassen an dem jeweils eine der verschiedenen Einrichten so nah wie möglich ist.
Dieses Problem ist ist durch ds farthest color Voronoi Diagramm lösbar.

Wir unterscheiden zwischen Voronoi Diagrammen (VD) und farthest color Voronoi Diagrammen (FCVD). Für den Fall das multiplikative Gewichte von Sites von Interesse sind, sprechen wir von gewichteten Voronoi Diagrammen (WVD) und weighted farthest color Voronoi Diagrammen (WFCVD).
Desweiteren unterscheiden wir zwischen Bäumen und Graphen, denn im Falle von Bäumes kann wir einen weniger komplexen Algorithmus zum berechnen des erwünschten Voronoi Diagrammes anwenden. Zusammenfassend kommen wir somit auf acht verschiedene Algorithmen, die in den hier vorgestellten Applets zur Anwendung kommen.

Benutzung der Applets

Zur Vereinfachung haben wir zwei seperate Applets erstellt. VDApplet benutzt die Algorithen der normalen Voronoi Diagramme, FCVDApplet zeigt die farthest color Variante. Beide Applets bieten die Option des gewichteten Falles, wobei an jeder Sites ein multiplikatives Gewicht eingestellt werden kann.

Der Graph Editor beider Applets erlaubt das Erstellen von Bäumen und Graphen. Sites können an jeder Kante durch einen einfachen Klick angebracht werden. Ein Rechtklick auf eine beliebige Komponente des Graphen öffnet das Kontextmenü, in dem die Eigenschaften angepasst oder die gesamte Komponente entfernt werden kann. Ein Rechtsklich auf eine leere Fläche des Editor öffnet das Editor Kontextmenü. Einige Optionen sind ausgeblendet, da diese nur im Application-Modus (Zugang auf das Dateisystem) benutzt werden können. Im Menü kann man einen neuen Graphen erstellen (Achtung: Nur ungerichtete Graphen erstellen um eine korrekte Voronoiberechnung sicherzustellen) sowie die Defaultwerte der Eigenschaften der jeweiligen Komponente einstellen. Die neuen Defaultwerte gelten für alle danach erstellten Komponenten.

Unter dem Editor ist eine Checkbox zum ein- und ausschalten der gewichteten Voronoi Diagrame. Auf der rechten Site bekommt man eine kunze Information über den Graphen der aktuell gezeichnet wird sowie über den angewanten Algorithmus zur Berechnung des Voronoidiagramms. Die Algorithmen wechseln automatisch entsprechend dem Layout des Graphen; ist der aktuelle Graph ein Baum, wird der entsprechende Tree-Algorithmus dem komplexeren Graph- Algorithmus bevorzugt.

Am unteren Rand befinden sich Algorithmus-spezifische Optionen, mit denen man sich zusätzliche Informationen über das aktuell berechnende Voronoi Diagramm anzeigen lassn kann.


(Gewichtete) Voronoi Diagramme

Für den Fall k=1 wird angenommen, dass alle n Sites die selbe Farbe besitzen. (Natürlich kann jede Site eine unterschiedliche gezeichnete Farbe haben, dies hat jedoch nur den Zweck die verschiedenen Sites mit ihren entsprechenden Bisektoren auseinanderhalten zu können. Die Algorithmen ignorieren diese Farbeigenschaften.) Dieses Applet berechnet die Voronoi Partition eines editieren Graphen und stellt diese dar. Fall erwünscht, werden die Gewichte der Sites mit berücksichtigt. Je nach Typ und Gewichtung des Graphen wird einer der folgenden Algorithmen verwendet (der jeweils aktive Algorithmus wird im Infofeld des Applets angezeigt):

[applet could not be started]

Die zusätzlichen Anzeigeoptionen


(Gewichtete) farthest color Voronoi Diagramme

Der Algorithmus dieses Applets berechnet zunächst den Parameter k als Anzahl der verschiedenen Farben die für die Sites benutzt werden. Dies geschieht vor der eigentlichen Berechnung des farthest color Voronoi Diagrammes. Die Menge der Sites wird in Untermengen gleicher Farbe eingeteilt. Die führt zu k verschiedenen unteren Konturen, aus denen dann die oberen Konturen berechnet werden. Je nach Typ und Gewichtung des Graphen wird einer der folgenden Algorithmen verwendet (der jeweils aktive Algorithmus wird im Infofeld des Applets angezeigt): This Applet's algorithms first determine the parameter k as the number of different colors used for the sites, before the farthest color Voronoi diagram is computet. The set of sites is divided into subsets with each subset's sites having the same color. This leads to k different lower envelopes, of which the upper envelope has to be computet. Depending on the type of graph and weighted mode, one of the following algorithms is used (the used algorithm is displayed in the applet's info field):

[applet could not be started]

Die zusätzlichen Anzeigeoptionen

Die Algorithmen nutzen für die Berechnung Distanzfunktionen der Sites (weitere Informationen hierzu finden sie in [1]). Diese Distanzfunktionen, ihre unteren Konturen, die linken und rechten Arme (im ungewichteten Fall) und die aus den unteren Konturen berechneten obere Konturen können angezeigt werden.

Literatur:

[1]:Ferran Hurtado, Rolf Klein, Elmar Langetepe, Vera Sacristán. The weighted farthest color Voronoi diagram on trees and graphs. August 14, 2002.