Map-Matching Queries Under Fréchet Distance on Low-Density Spanners
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Documents
- Fulltext
Final published version, 1.73 MB, PDF document
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.
Original language | English |
---|---|
Title of host publication | 40th International Symposium on Computational Geometry, SoCG 2024 |
Editors | Wolfgang Mulzer, Jeff M. Phillips |
Number of pages | 15 |
Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |
Publication date | 2024 |
Article number | 27 |
ISBN (Electronic) | 9783959773164 |
DOIs | |
Publication status | Published - 2024 |
Event | 40th International Symposium on Computational Geometry, SoCG 2024 - Athens, Greece Duration: 11 Jun 2024 → 14 Jun 2024 |
Conference
Conference | 40th International Symposium on Computational Geometry, SoCG 2024 |
---|---|
Land | Greece |
By | Athens |
Periode | 11/06/2024 → 14/06/2024 |
Series | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|
Volume | 293 |
ISSN | 1868-8969 |
Bibliographical note
Publisher Copyright:
© Kevin Buchin, Maike Buchin, Joachim Gudmundsson, Aleksandr Popov, and Sampson Wong.
- Data Structures, Fréchet Distance, Map Matching
Research areas
ID: 395152925