Straight Skeletons, polygonale und polyedrische Offsets

Das Vergroessern und Verkleinern von Polygonen und Polyedern ist eine fast unerschoepfliche Quelle fuer wichtige praktische Probleme der Algorithmischen Geometrie. In Vorarbeiten hat der Antragsteller den derzeit defakto weltweit fuehrenden Algorithmus zum Berechnen von Parallelkurven ("Offsets") von polygonalen Taschen entwickelt, welcher auf seinem robusten und effizienten Programm "VRONI" zum Berechnen von Voronoi Diagrammen basiert. In diesem Projektantrag wird eine weitere Vertiefung der Wechselbeziehungen zwischen der Generierung von Offsets und Voronoi-aehnlichen Skeletten vorgeschlagen, in dem basierend auf der bisherigen Erfahrung des Antragsstellers mit der Berechnung von Offsets neue Algorithmen zur Generierung von rein polygonalen und polyedrischen Offsets entwickelt werden. Im Gegensatz zu Standard-Offsets bedeutet dies, dass Polygone und Polyeder so vergroessert bzw. verkleinert werden, dass das resultierende Objekt wieder ein Polygon oder ein Polyeder ist; Standard-Offsets wuerden hingegen auch Kreisboegen oder gekruemmte Flaechen beinhalten. Derartig rein polygonale Offsets sind etwa fuer die Werkzeugweggenerierung von Bedeutung, wenn verhindert werden muss, dass ein Werkzeug bei einer Bewegung um eine Ecke zu lange mit dieser Ecke in Kontakt bleibt. In juengerer Zeit erarbeitete neue Erkenntnisse betreffend die sogenannte "Linear Axis" sowie zur Berechnung von Offsets mit abgefasten Ecken suggerieren, dass es moeglich sein sollte, Algorithmen zur rein polygonalen/polyedrischen Offset-Berechnung zu entwickeln, welche eine geringere Komplexitaet als die derzeit bekannten und in der Praxis eingesetzten Algorithmen aufweisen. Um unsere Algorithmen so allgemein wie moeglich zu halten, werden wir nicht auf eine spezielle Anwendung (wie etwa die Werkzeugweggenerierung) fokusieren, sondern uns insbesondere den mit der Offset-Generierung verbundenen Datenstrukturen der Algorithmischen Geometrie zu wenden: "Straight Skeletons" und "Linear Axis". Obwohl das Basiskonzept eines Straight Skeleton bereits vor mehr als zehn Jahren vorgestellt wurde, sind selbst im 2D immer noch eine Reihe wichtigen Fragn offen; im 3D ist dazu im wesentlichen noch gar nichts bekannt. Insbesondere gibt es bisher nicht einmal fuer 2D ein wirklich stabiles und korrektes Programm zur Berechnung eines Straight Skeleton, welches auch einfach als einzelner Modul benutzt werden kann. Abgesehen von der Erarbeitung einer soliden algorithmischen Basis fuer rein polygonale/polyedrische Offsets werden wir unser Augenmerk auch ganz wesentlich der Ueberfuehrung unserer Algorithmen in entsprechende eigenstaendige Programmmodule widmen. Die Bereitstellung von zuverlaessigen und effizienten Programmen ist nicht nur ein wichtiger Dienst an der Forschergemeinde, sondern stellt insbesondere fuer unsere zweite Zielgruppe -- die Anwender in Industrie und Gewerbe -- meist eine wesentliche und unabdingbare Voraussetzung fuer den tatsaechlichen Einsatz neuer Algorithmen dar. Wobei unsere Algorithmen natuerlich nicht auf Werkzeugweggenerierung beschraenkt sind, sondern neben CAD/CAM und GIS in vielen technisch/naturwissenschaftlichen Gebieten zum Einsatz kommen koennen.