Sichtbarkeit in triangulierten planaren Unterteilungen

Abstract

In dieser Arbeit wird ein neuer Algorithmus für eine effiziente Berechnung der sichtbaren Hindernisecken in einem euklidischen Raum mit Hindernissen vorgestellt. Dieser Algorithmus wird anschließend dazu vewendet, einerseits den vollständigen Sichtbarkeitsgraphen und andererseits mithilfe eines Dijkstra-basierten Verfahrens den kürzesten Pfad in einem euklidischen Raum mit Hindernissen zu ermitteln. Die hier vorgestellten Algorithmen werden, im Gegensatz zu den Ansätzen aus früheren Papern, auf einem klassischen Rechner implementiert und ihre Laufzeiten werden mit denen der naiven Verfahren verglichen.