2024/07/27 by Kevin Buchin, Buchin, Kevin, Maike Buchin +7 · 2 citations
Computer Science · #Caching and Content Delivery #Computational Geometry (cs.CG) #Data Management and Algorithms #F.2.2 #FOS: Computer and information sciences #G.2.2 #I.3.5 #Network Packet Processing and Optimization
paper · pdf · doi:10.48550/arxiv.2407.19304
openalex publication_date 2024/07/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 [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 λ-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.