Navigationssysteme und Verkehrsschätzungen spielen eine entschei- dende Rolle im täglichen Leben, indem sie die Reisezeit verkürzen, den Kraftstoffverbrauch minimieren und die Sicherheit durch die Bereitstel- lung von Echtzeit-Verkehrsinformationen und optimalen Routen erhöhen. Ein wesentlicher Bestandteil dieser Systeme ist das Map-Matching, das rohe GPS-Koordinaten mit den entsprechenden Straßen auf einer digitalen Karte abgleicht. Diese Arbeit untersucht drei Hauptklassen von Map- Matching-Algorithmen: geometrische, max-weight und hybride Ansätze. Die Arbeit untersucht drei unterschiedliche Ansätze: zwei Max-Weight- Methoden basierend auf Hidden Markov Modellen, von denen eine eine Geschwindigkeitssteigerung durch Routen-Vorberechnung einbezieht, und eine hybride Methode, die die vertex-monotone Fréchet-Distanz verwen- det. Die theoretischen Grundlagen und die Laufzeitanalyse des Algorith- mus zur vertex-monotonen Fréchet-Distanz werden detailliert diskutiert. Ein wesentlicher Beitrag dieser Arbeit ist die Implementierung des Al- gorithmus zur vertex-monotonen Fréchet-Distanz in Rust, begleitet von einem Visualisierungstool, das die Überprüfung sowohl der abgeglichenen als auch der ursprünglichen Trajektorien ermöglicht.

Darüber hinaus präsentiert die Arbeit eine empirische Bewertung dieser Ansätze, mit einem Fokus auf Laufzeiten, Matching-Anteile und Trajekto- rienformen. Die Analyse umfasst Visualisierungen und Diskussionen zu verschiedenen Algorithmusparametern, wie räumlichen Strukturen, Toler- anzdistanzen und Gewichtungsfaktoren. Die primären Vergleichsmetriken sind Laufzeiten und Matching-Anteile, ergänzt durch manuelle Überprü- fungen der Routenformen mithilfe des Visualisierungstools.