Master thesis : Umwegprobleme in Graphen und Polygonen
Advisor: Prof. Dr. Christian Knauer
In meiner Arbeit geht es darum, Umwege in Triangulierungen von planaren Punktmengen zu untersuchen.
Ist P eine planare Punktmenge und T eine Triangulierung von P, so kann man für zwei Punkte u, v in P zwei verschiedene Arten von Abständen betrachten: zum einen wäre da die Länge eines kürzesten Weges von u nach v entlang den Kanten von T. Zum anderen kann man sich auch den euklidischen Abstand zwischen u und v ansehen. Der Umweg zwischen u und v ist dann definiert als der Quotient zwischen der Länge des kürzesten Weges von u nach v und dem euklidischen Abstand. Der Umweg ist ein natürliches Maß dafür, wie gut u und v durch T miteinander verbunden sind. Die graphentheoretische Dilatation von T ist der maximale Umweg, der zwischen zwei Knoten in T auftreten kann.
Es geht nun darum, zu untersuchen, welche Triangulierungen einer gegebenen Punktmenge die optimale graphentheoretische Dilatation erreichen und wie solche Triangulierungen effizient berechnet werden können.