2026-08-10T23:24:06Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14879 2024-03-06T10:31:35Z ddc:004 open_access

Fast Map Matching with Vertex-Monotone Fréchet Distance Chen, Daniel Sommer, Christian Wolleb, Daniel Fréchet distance map matching minimum bottleneck path We study a generalization for map matching algorithms that includes both geometric approaches such as the Fréchet distance and global weight approaches such as those typically used by Hidden Markov Models. Through this perspective, we discovered an efficient map matching algorithm with respect to the vertex-monotone Fréchet distance while using a heuristic tie-breaker inspired by global weight methods. While the classical Fréchet distance requires parameterizations to be monotone, the vertex-monotone Fréchet distance allows backtracking within edges. Our analysis and experimental evaluations show that relaxing the monotonicity constraint enables significantly faster algorithms without significantly altering the resulting map matched paths. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Daniel Chen and Christian Sommer and Daniel Wolleb 2021 Is Part Of OASIcs, Volume 96, 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/OASIcs.ATMOS.2021.10 urn:nbn:de:0030-drops-148794 https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2021.10 eng https://creativecommons.org/licenses/by/4.0/legalcode