Betreuer: Bertold Bongardt

Das Problem der kürzesten Wege und dazu geeignete Lösungsmethoden sind besonders bekannt für diskrete Graphen, etwa zur Berechnung von Wegen in Verkehrsnetzen. In der Robotik können zur Bewegungsplanung nicht nur endlich viele Wege (Kanten eines Graphen) benutzt werden, sondern unendlich viele. Damit kann ein robotisches Problem der kürzesten Wege als ein 'Euklidisches kürzeste Wege Problem' modelliert werden. Werden Hindernisse in erster Approximation als linear beschränkte unzugängliche Bereiche angesehen, ist das zugrundeliegende Wege-Problem gekennzeichnet als 'kürzeste Wege Problem auf polyedrischen Oberflächen'. Als Einstieg in die Thematik kann gut der Übersichtsartikel 'A survey of geodesic paths on 3D surfaces' von Bose, Maheshwari, Shu und Wuhrer (2011) herangezogen werden. In dieser Seminararbeit soll die Funktionsweise der beiden bekanntesten Methoden zur Lösung des Problems, der des Algorithmus von Chen und Han und der des Continuous Dijkstra Algorithmus, miteinander verglichen werden.