Gewichtete Voronoi Diagramme: Geometrische Deutung und Konstruktions-Algorithmen

F. Aurenhammer

Abstract:

Das oft als Computational Geometry bezeichnete Teilgebiet der Computerwissenschaften beschaeftigt sich mit der algorithmischen Loesung elementargeometrischer Probleme. Einen Schwerpunkt in der Computational Geometry bildet die Untersuchung von Abstandsproblemen. In diesem Zusammenhang spielt das Voronoi Diagramm einer endlichen Punktmenge eine zentrale Rolle. Die vorliegende Arbeit ist eine geometrische und algorithmische Studie sogenannter gewichteter Voronoi Diagramme. Diese Diagramme leiten sich aus dem Original durch Ersetzen des Euklidabstandes durch individuell gewichtete Abstaende her. Das Anwendungsspektrum solcher Konzepte umfasst die Wissenschaften Geographie, Oekonomie, Biologie, Mathematik, Physik und Chemie. Die Hauptergebnisse dieser Arbeit sind die Erforschung der Verwandtschaft gewichteter Diagramme zu anderen geometrischen Objekten (konvexe Huellen, Zellkomplexe und Arrangements) mit Hilfe geometrischer Transformationen, und der Entwurf effizienter Algorithmen fuer ihre Konstruktion. Ein Teil der Resultate wurde bereits in Schnelldruckserien und wissenschaftlichen Journalen veroeffentlicht.

Reference: F. Aurenhammer. Gewichtete Voronoi Diagramme: Geometrische Deutung und Konstruktions-Algorithmen. PhD thesis, IIG-TU Graz, Austria, 1984. Report B53.