Map-Matching Queries Under Fréchet Distance on Low-Density Spanners
Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Standard
Map-Matching Queries Under Fréchet Distance on Low-Density Spanners. / Buchin, Kevin; Buchin, Maike; Gudmundsson, Joachim; Popov, Aleksandr; Wong, Sampson.
40th International Symposium on Computational Geometry, SoCG 2024. red. / Wolfgang Mulzer; Jeff M. Phillips. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2024. 27 (Leibniz International Proceedings in Informatics, LIPIcs, Bind 293).Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - GEN
T1 - Map-Matching Queries Under Fréchet Distance on Low-Density Spanners
AU - Buchin, Kevin
AU - Buchin, Maike
AU - Gudmundsson, Joachim
AU - Popov, Aleksandr
AU - Wong, Sampson
N1 - Publisher Copyright: © Kevin Buchin, Maike Buchin, Joachim Gudmundsson, Aleksandr Popov, and Sampson Wong.
PY - 2024
Y1 - 2024
N2 - 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 [13] 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.
AB - 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 [13] 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.
KW - Data Structures
KW - Fréchet Distance
KW - Map Matching
U2 - 10.4230/LIPIcs.SoCG.2024.27
DO - 10.4230/LIPIcs.SoCG.2024.27
M3 - Article in proceedings
AN - SCOPUS:85195460048
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 40th International Symposium on Computational Geometry, SoCG 2024
A2 - Mulzer, Wolfgang
A2 - Phillips, Jeff M.
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 40th International Symposium on Computational Geometry, SoCG 2024
Y2 - 11 June 2024 through 14 June 2024
ER -
ID: 395152925