Die PG Graphalgorithmen wird im Sommersemester 2023 zusammen mit der PG Algorithm Engineering zusammengelegt. Informationen dazu finden Sie hier: Projektgruppe: Algorithm Engineering (Polygonalisierung von Punktmengen).

Das dort studierte Problem kann sehr schön als ein Tourenplanungsproblem in einem Graphen modelliert werden. Sei S die Punktmenge, dann können wir den vollständigen Graphen G=(S,E) betrachten, wobei die Kantengewichte gegeben sind durch die euklidischen Distanzen. Eine Polygonalisierung der Punktmenge ist dann ein Hamiltonkreis auf diesem Graph (unter der Nebenbedingung das sich die “geometrischen” eingebetteten Kanten nicht schneiden).

Interessanterweise ist das Euklidische Traveling Salesperson Problem ein Spezialfall von optimalen Polygonalisierungen. Man sucht nämlich genau den Hamiltonkreis/die Tour/die Polygonalisierung, welche die Länge der Tour/den Umfang des Polygons minimiert.

Wir wollen in der PG andere Optimalitätsmaße betrachten (die ein wenig geometrischer sind), aber die Methoden sind motiviert durch die Methoden vom euklidischen TSP.

Die benötigte Algorithmische Geometrie ist dabei sehr “elementar”.

Wichtig: Wenn Sie an der Projektgruppe teilehmen möchten, schreiben Sie bitte bis zum 28.2.23 eine formlose Anmeldung per Email an Philip Mayer, damit wir die zu erwartende Teilnehmerzahl abschätzen können. Die Teilnehmerzahl ist auf sechs Teilnehmer beschränkt.