Map-Matching Queries Under Fréchet Distance on Low-Density Spanners
Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
Dokumenter
- Fulltext
Forlagets udgivne version, 1,73 MB, PDF-dokument
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.
Originalsprog | Engelsk |
---|---|
Titel | 40th International Symposium on Computational Geometry, SoCG 2024 |
Redaktører | Wolfgang Mulzer, Jeff M. Phillips |
Antal sider | 15 |
Forlag | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |
Publikationsdato | 2024 |
Artikelnummer | 27 |
ISBN (Elektronisk) | 9783959773164 |
DOI | |
Status | Udgivet - 2024 |
Begivenhed | 40th International Symposium on Computational Geometry, SoCG 2024 - Athens, Grækenland Varighed: 11 jun. 2024 → 14 jun. 2024 |
Konference
Konference | 40th International Symposium on Computational Geometry, SoCG 2024 |
---|---|
Land | Grækenland |
By | Athens |
Periode | 11/06/2024 → 14/06/2024 |
Navn | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|
Vol/bind | 293 |
ISSN | 1868-8969 |
Bibliografisk note
Funding Information:
Aleksandr Popov: Supported by the Dutch Research Council (NWO) under the project number 612.001.801. Sampson Wong: Supported in part by Starting Grant 1054-00032B from the Independent Research Fund Denmark under the Sapere Aude research career programme.
Publisher Copyright:
© Kevin Buchin, Maike Buchin, Joachim Gudmundsson, Aleksandr Popov, and Sampson Wong.
ID: 395152925