Map Matching Queries Under Fréchet Distance on Low-Density Spanners

Map matching is a common task when analysing GPS tracks, like vehicle trajectories - the goal is to match a recorded noisy polygonal curve to a path on the map, usually represented as a geometric graph. 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 have studied this problem for arbitrary query polygonal curves and c-packed graphs. In this abstract, we relax the requirement on graphs to be λ-low-density t-spanners, more closely corresponding to real-world networks. We also show how to report a path that minimises the distance efficiently rather than only return the minimal distance.