Mediale Achsen und Voronoj-Diagramme in der euklidischen Ebene

Abstract

Die mediale Achse wurde 1967 von Harry Blum zur Darstellung und Analyse ebener abgeschlossener Gebiete eingeführt. Sie besteht aus dem Abschluß der Menge aller Mittelpunkte maximaler Kreisscheiben. Eine Kreisscheibe heißt dabei maximal, sofern sie ganz in dem Gebiet enthalten und nicht echte Teilmenge einer ebenfalls in dem zu betrachtenden Gebiet liegenden Kreisscheibe ist. Auf der medialen Achse operiert die Radiusfunktion. Sie ordnet jedem Punkt der medialen Achse den Radius der zugehörigen maximalen Kreisscheibe zu und ermöglicht damit die exakte Rekonstruktion des zugrundeliegenden Gebietes aus der medialen Achse. Die mediale Achse ist lokale Symmetrieachse, dimensionsreduzierend und führt auf einen Graphen, welcher mit Hilfe der metrischen Informationen der Radiusfunktion eine automatisierte Analyse ebener Gebiete mittels graphentheoretischer Konzepte ermöglicht. Die Arbeit faßt zunächst alternative Definitionen, Eigenschaften und Anwendungsgebiete medialer Achsen zusammen. Im Vordergrund steht jedoch die exakte Berechnung beziehungsweise die Approximation medialer Achsen abgeschlossener Gebiete in der euklidischen Ebene. Entscheidendes Hilfsmittel ist hierbei das Voronoj-Diagramm - jene Partition der euklidischen Ebene, die jedem Punkt einer vorgegebenen Menge diejenigen Punkte der euklidischen Ebene zuordnet, deren Abstände zu diesem kleiner als zu allen anderen Punkten der besagten Menge sind. Der Begriff des Voronoj-Diagramms von Punktmengen wird hierzu auf Mengen von Geradensegmenten und Punkten erweitert. Es wird gezeigt, daß die mediale Achse eines polygonalen Gebietes eine einfach zu charakterisierende Teilmenge des verallgemeinerten Voronoj-Diagramms des Randpolygons ist und im Fall konvexer polygonaler Gebiete mit diesem übereinstimmt. Der zweite Teil der Arbeit befaßt sich mit der Approximation medialer Achsen r-regulärer Mengen mit Hilfe des Voronoj-Diagramms einer auf dem Rand verteilten diskreten Punktmenge.