2026-07-24T17:55:14Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19972 2024-06-06T06:21:14Z ddc:004 open_access

Map-Matching Queries Under Fréchet Distance on Low-Density Spanners Buchin, Kevin Buchin, Maike Gudmundsson, Joachim Popov, Aleksandr Wong, Sampson Map Matching Fréchet Distance Data Structures Map matching is a common task when analysing GPS tracks, such as vehicle trajectories. The goal is to match a recorded noisy polygonal curve to a path on the map, usually represented as a geometric graph. The Fréchet distance is a commonly used metric for curves, making it a natural fit. The map-matching problem is well-studied, yet until recently no-one tackled the data structure question: preprocess a given graph so that one can query the minimum Fréchet distance between all graph paths and a polygonal curve. Recently, Gudmundsson, Seybold, and Wong [Gudmundsson et al., 2023] studied this problem for arbitrary query polygonal curves and c-packed graphs. In this paper, we instead require the graphs to be λ-low-density t-spanners, which is significantly more representative of real-world networks. We also show how to report a path that minimises the distance efficiently rather than only returning the minimal distance, which was stated as an open problem in their paper. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Kevin Buchin and Maike Buchin and Joachim Gudmundsson and Aleksandr Popov and Sampson Wong 2024 Is Part Of LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2024.27 urn:nbn:de:0030-drops-199723 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.27 eng https://creativecommons.org/licenses/by/4.0/legalcode