Map-Matching Queries under Fr\'echet Distance on Low-Density Spanners
<|reference_start|>Map-Matching Queries under Fr\'echet Distance on Low-Density Spanners: 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\'echet 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\'echet distance between all graph paths and a polygonal curve. Recently, Gudmundsson, Seybold, and Wong [SODA 2023, arXiv:2211.02951] studied this problem for arbitrary query polygonal curves and $c$-packed graphs. In this paper, we instead require the graphs to be $\lambda$-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.<|reference_end|>
@article{buchin2024map-matching,
    title={Map-Matching Queries under Fr\'echet Distance on Low-Density Spanners},
    author={Kevin Buchin, Maike Buchin, Joachim Gudmundsson, Aleksandr Popov, and
  Sampson Wong},
    journal={arXiv preprint arXiv:2407.19304},
    year={2024},
    archivePrefix={arXiv},
    eprint={2407.19304},
    primaryClass={cs.CG}
}