Skip to Main content Skip to Navigation
Conference papers

Minimizing Walking Length in Map Matching

Abstract : In this paper, we propose a geometric algorithm for a map matching problem. More specifically, we are given a planar graph, H, with a straight-line embedding in a plane, a directed polygonal curve, T, and a distance value $\varepsilon >0$. The task is to find a path, P, in H, and a parameterization of T, that minimize the sum of the length of walks on T and P whereby the distance between the entities moving along P and T is at most $\varepsilon $ε, at any time during the walks. It is allowed to walk forwards and backwards on T and edges of H. We propose an algorithm with $\mathcal {O}\left( mn \left( m+n\right) \log (mn)\right) $ time complexity and $\mathcal {O}\left( mn \left( m+n\right) \right) $ space complexity, where m (n, respectively) is the number of edges of H (of T, respectively). As we show, the algorithm can be generalized to work also for weighted non-planar graphs within the same time and space complexities.
Document type :
Conference papers
Complete list of metadata

Cited literature [15 references]  Display  Hide  Download
Contributor : Hal Ifip Connect in order to contact the contributor
Submitted on : Wednesday, January 25, 2017 - 4:51:01 PM
Last modification on : Thursday, January 26, 2017 - 9:30:23 AM
Long-term archiving on: : Wednesday, April 26, 2017 - 3:49:47 PM


Files produced by the author(s)


Distributed under a Creative Commons Attribution 4.0 International License



Amin Gheibi, Anil Maheshwari, Jörg-Rüdiger Sack. Minimizing Walking Length in Map Matching. 1st International Conference on Theoretical Computer Science (TTCS), Aug 2015, Tehran, Iran. pp.105-120, ⟨10.1007/978-3-319-28678-5_8⟩. ⟨hal-01446266⟩



Record views


Files downloads