  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.
