Diplom-/Masterarbeit : Kontrollpfadanfragen in einfachen Polygonen
Betreuer: Prof. Dr. Christian Knauer
Gegeben sei ein einfaches Polygon P und ein fester Startpunkt s ∈ P . Das Polygon P soll so vorverarbeitet werden, dass der kürzeste Weg, der bei s startet und von dem ein Anfragepunkt q ∈ P zu sehen ist, schnell bestimmt werden kann. Es wird ein Algorithmus vorgestellt, der eine Verbesserung zu den bisher bekannten Algorithmen darstellt. Hauptbestandteil der Arbeit ist es aber effiziente Algorithmen zu entwerfen, die dieses Problem für zwei Anfragepunkte lösen.
Desweiteren werden mehrere Approximationsalgorithmen präsentiert.