Geodätische Voronoi-Diagramme

Hannes Thielhelm, Leibniz Universität Hannover, diploma thesis
04/2007

Voronoi-Diagramme finden seit ihrer Einführung durch Georgi Voronoi 1905 in sehr vielen Bereichen der Wissenschaft, wie Biologie, Medizin und natürlich auch Mathematik und Informatik verschiedenste Anwendungen. Sie liefern auf natürliche Weise eine Partitionierung des umgebenden Raums in Bezug auf den Abstand zu gegebenen Referenzobjekten (meistens Punkte).

In dieser Arbeit werden Voronoi-Diagramme in dreidimensionalen metrischen Räumen berechnet. Der Abstandsbegriff wird hier durch das Konzept der Metrik verallgemeinert. Dabei wird die gegebene Metrik durch den Abstandsbegriff auf einer im vierdimensionalen eingebetteten dreidimensionalen Höhenfläche induziert. Schwerpunkt der Arbeit ist die Entwicklung eines Verfahrens zur Berechnung von geodätischen Voronoi-Diagrammen, das ohne Verschneidungsalgorithmen auskommt. Dies wird durch ein Perturbationsverfahren erreicht, das die Berechnung der Knoten, d.h. der Punkte des Voronoi-Diagramms, zu denen mindestens vier Referenzpunkte gleichen Abstand haben, ermöglicht. Dabei wird eine homotope Deformation der euklidischen Metrik hin zur gegebenen Metrik durchgeführt.

Kontakt: Henning Naß