 |
[]
[] []
|
|
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.
Mehr Informationen über gewichtete farthest color Voronoi Diagramme
auf Bäumen und Graphen, inklusive Komplexitäten Algorithmen und findet man im folgenden Paper:
WFCVD (PS, unzipped, 214K)
WFCVD (PS, g-zipped, 71K)
WFCVD (PDF, unzipped, 545K)
WFCVD (PDF, g-zipped, 163K)
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):
- VDTree - comput. O(m + n log n)
- VDGraph - comput. O(e + n log n + m log m)
- WVDTree - comput. O(mn log n)
- WVDGraph - comput. O(en log n + mn log m)
Die zusätzlichen Anzeigeoptionen
- VDTree - Spannbaum: Der Spannbaum aller Sites kann angezeigt werden.
(der Algorithmus nutzt den Spannungbaum zur Beschleunigung der Berechnung)
- VDGraph - übriger Graph: Die inneren Sites aller Kanten werden
vor der Berechnung entfernt, sie ergeben den übrigen Graph.
- WVDTree/Graph: Die Algorithmen nutzen für die Berechnung Distanzfunktionen der Sites
(weitere Informationen hierzu finden sie in dem oben genannten paper).
Diese Distanzfunktionen oder ihre untere Kontur können angezeigt werden.
(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):
- FCVDTree - comput. O(km + n log n)
- FCVDGraph - comput. O(ke log k + n log n + km log m)
- WFCVDTree - comput. O(mn(log n + ack2(k) log k))
- WFCVDGraph - comput. O(en(log n + ack2(k) log k) + mn log m)
Die zusätzlichen Anzeigeoptionen
Die Algorithmen nutzen für die Berechnung Distanzfunktionen der Sites
(weitere Informationen hierzu finden sie in dem oben genannten Paper).
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.
Bibliography
Ferran Hurtado, Rolf Klein, Elmar Langetepe, Vera Sacristán.
The weighted farthest color Voronoi diagram on trees and graphs. August 14,
2002.
