1. Map-Matching Queries under Fr\'echet Distance on Low-Density Spanners
- Author
-
Buchin, Kevin, Buchin, Maike, Gudmundsson, Joachim, Popov, Aleksandr, and Wong, Sampson
- Subjects
Computer Science - Computational Geometry ,F.2.2 ,G.2.2 ,I.3.5 - Abstract
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., Comment: This is an extended version of the article published in SoCG 2024, doi:10.4230/LIPIcs.SoCG.2024.27. 15 pages, 4 figures
- Published
- 2024