Map-Matching Queries under Fréchet Distance on Low-Density Spanners
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917735468892160 |
|---|---|
| author | Buchin, Kevin Buchin, Maike Gudmundsson, Joachim Popov, Aleksandr Wong, Sampson |
| author_facet | Buchin, Kevin Buchin, Maike Gudmundsson, Joachim Popov, Aleksandr Wong, Sampson |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_19304 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Map-Matching Queries under Fréchet Distance on Low-Density Spanners Buchin, Kevin Buchin, Maike Gudmundsson, Joachim Popov, Aleksandr Wong, Sampson Computational Geometry F.2.2; G.2.2; I.3.5 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. |
| title | Map-Matching Queries under Fréchet Distance on Low-Density Spanners |
| topic | Computational Geometry F.2.2; G.2.2; I.3.5 |
| url | https://arxiv.org/abs/2407.19304 |