Schnelle dynamische Voronoi-Diagramme mit History-DAG

Richard Algaier, Leibniz Universität Hannover, diploma thesis
03/2010

Das Voronoi Diagramm ist eine fundamentale räumliche Struktur, die sich in vielen Bereichen des täglichen Lebens wiederfindet, bei denen räumliche Abhängigkeiten und Nachbarschaftsbeziehungen eine Rolle spielen. Sie wird deshalb von vielen wissenschaftlichen Disziplinen, vor allem in ingenieurs- und naturwissenschaftlichen Bereich, zur Lösung unterschiedlichster Problemstellungen verwendet.

Ziel dieser Arbeit ist es, schnelle dynamische Voronoi-Diagramme mit einer Simplex-Datenstruktur im 3-dimensionalen zu erstellen. Mit „dynamisch“ ist gemeint, dass die vorhandene Punktmenge in zwei neue aufgeteilt wird, die dann voneinander weg bewegt werden sollen. Durch die Verschiebung der Punkte verändert sich auch das Voronoi-Diagramm. Der zu entwickelnde Algorithmus soll eine schnelle, d.h. möglichst effiziente Erstellung des neuen Voronoi-Diagramms nach der Verschiebung ermöglichen.

Im Rahmen dieser Arbeit wird geprüft, ob eine effiziente Erstellung des Voronoi-Diagramms nach der Verschiebung durch einen Rückgriff auf bereits vorhandene Ergebnisse möglich ist. D.h. es werden nur für die Stellen neue Berechnungen angestellt, an denen sich durch die Verschiebung topologische Veränderungen im Voronoi-Diagramm ergeben haben.

Aufgrund der einfacheren Berechenbarkeit wird nicht das Voronoi-Diagramm, sondern die duale Delaunay-Tesselierung erstellt. Diese wird mit Hilfe numerisch stabiler Prädikate und eines robusten Flipping-Algorithmus berechnet.

Contact: Philipp Blanke