Deutsch English

Schwerpunkt-Voronoi-Diagramme

Das Thema Scherpunkt-Voronoi-Diagramme (Centroidal Voronoi Diagrams/Tesselations) wurde im Rahmen einer Diplomarbeit an der FernUniversität Hagen im Fachbereich Informatik, Lehrgebiet Praktische Informatik VI bearbeitet. Betreut wurde die Arbeit von Dr. Christian Icking und Dr. Lihong Ma.

Nachfolgend wird eine kurze Einführung in das Thema gegeben; eine umfassende Darstellung kann der Diplomarbeit entnommen werden.

Schwerpunkt-Voronoi-Diagramme

Schwerpunkt-Voronoi-Diagramme sind zuerst einmal Voronoi-Diagramme:

Voronoi-Diagramme

Das Voronoi-Diagramm zerlegt einen gegebenen Raum bei einer ebenfalls gegebenen Punktmenge in Regionen. Jedem dieser Punkte – genannt Voronoi-Punkt – ist genau eine Region zugeordnet. Die Regionen haben die wesentliche Eigenschaft, dass alle Punkte einer Region ihrem Voronoi-Punkt näher sind als allen anderen Voronoi-Punkten.

Die folgende Abbildung illustriert dies für 256 Punkte; die Kreuze sind die Voronoi-Punkte, die Linien die Regionsgrenzen. Ergänzend sind die Schwerpunkte der auf den gelben Bereich beschränkten Voronoi-Regionen als Kreise eingetragen.

Schwerpunkt-Voronoi-Diagramme

Das Schwerpunkt-Voronoi-Diagramm ist ein Voronoi-Diagramm, bei dem die Voronoi-Punkte gleichzeitig Schwerpunkt ihrer Region sind. Dadurch ergibt sich eine interessante Eigenschaft des Schwerpunkt-Voronoi-Diagramms: Es ist in einem gewissen Sinne optimal.

Die folgende Abbilung zeigt ein einfaches Schwerpunkt-Voronoi-Diagramm in einer quadratischen Grundfläche, hier gelb eingefärbt. Es ist deutlich zu sehen, dass Voronoi-Punkte und Schwerpunkte zusammenfallen. Weiterhin fällt auf, dass beim Schwerpunkt-Voronoi-Diagramm die Voronoi-Punkte viel gleichmäßiger verteilt sind.

Weitere Schwerpunkt-Voronoi-Diagramme, insbesondere solche mit nicht konstanter Dichte und nicht quadratischer Grundfläche, befinden sich in Anhang B der Diplomarbeit.

Anwendung

Optimierung

Aus der Optimalitätseigenschaft des Schwerpunkt-Voronoi-Diagramms resultieren einige Anwendungsmöglichkeiten, von denen eine nachfolgend stark vereinfacht skizziert wird:

Gegeben sei ein Innenstadtbezirk. In diesem sollen Briefkästen unter Berücksichtigung der Einwohnerdichte optimal platziert werden. Optimal sei eine Verteilung genau dann, wenn die Summe der quadratischen Entfernungen aller Einwohner zu ihrem nächstgelegenen Briefkasten minimiert wird.

Die Lösung des Problems führt zu einem Schwerpunkt-Voronoi-Diagramm.

Für 256 Briefkästen und gleichmäßige Einwohnerdichte in einem quadratischen Innenstadtbereich könnte die Situation vor der Optimierung durch die erste und nach der Optimierung durch die zweite der oben stehenden Abbildung dargestellt sein.

Interaktive Demonstration

Java-Applet CentroidalVoronoi

Mit Klick auf Start! kann das Java-Applet CentroidalVoronoi gestartet werden. Mit seiner Hilfe lassen sich interaktiv Schwerpunkt-Voronoi-Diagramme berechnen.

Die Bedienung erfolgt intuitiv über Befehlsschaltflächen; zeigt die Maus längere Zeit auf eine solche, erscheint eine kurze englische Hilfe.

Eine umfangreiche Bedienungsanleitung kann Anhang A der Diplomarbeit entnommen werden.

 

 

Erweiterungen

Es ist grundsätzlich möglich, eigene Dichtefunktionen in das Applet einzubinden.

Ein Überblick über die verwendeten Java-Klassen findet sich hier.

CentroidalVoronoi kann als jar-Datei (ca. 179 kB) auch offline verwendet werden. Zum Starten genügt i. d. R. der Konsolenbefehl java -jar CentroidalVoronoi.jar.

Diplomarbeit

Lesefassung

Der vollständige Text der Diplomarbeit kann als pdf-Datei (ca. 5.4 MB) heruntergeladen werden. Die enthaltenen Grafiken sind zur Reduzierung der Dateigröße teilweise erheblich komprimiert und damit in der Qualität reduziert.

Alternativ kann die ganze Arbeit mit Einschränkungen als html-Seiten im Internet-Browser angesehen werden; Konvertierungsfehler des LaTeX2HTML-Konverters wurden nicht korrigiert.

Einen guten Überblick über die wesentlichen Punkte bietet die Präsentation als pdf-Datei (ca. 944 kB).

Quelltext LaTeX

Der LaTeX-Quelltext der Diplomarbeit kann beim Autor angefordert werden.

Quelltext CentroidalVoronoi

Der Java-Quelltext kann als tgz-Archiv (ca. 94 kB) heruntergeladen werden. Er steht – mit Ausnahme der Berechnung des Voronoi-Diagramms – unter der GNU General Public License. Nähere Informationen befinden sich in Anhang A der Diplomarbeit.

?

Christian Raskob