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.
Type de document :
Communication dans un congrès
Mohammed Taghi Hajiaghayi; Mohammad Reza Mousavi. 1st International Conference on Theoretical Computer Science (TTCS), Aug 2015, Tehran, Iran. Lecture Notes in Computer Science, LNCS-9541, pp.105-120, 2016, Topics in Theoretical Computer Science. 〈10.1007/978-3-319-28678-5_8〉
Liste complète des métadonnées

Littérature citée [15 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01446266
Contributeur : Hal Ifip <>
Soumis le : mercredi 25 janvier 2017 - 16:51:01
Dernière modification le : jeudi 26 janvier 2017 - 09:30:23
Document(s) archivé(s) le : mercredi 26 avril 2017 - 15:49:47

Fichier

 Accès restreint
Fichier visible le : 2019-01-01

Connectez-vous pour demander l'accès au fichier

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Amin Gheibi, Anil Maheshwari, Jörg-Rüdiger Sack. Minimizing Walking Length in Map Matching. Mohammed Taghi Hajiaghayi; Mohammad Reza Mousavi. 1st International Conference on Theoretical Computer Science (TTCS), Aug 2015, Tehran, Iran. Lecture Notes in Computer Science, LNCS-9541, pp.105-120, 2016, Topics in Theoretical Computer Science. 〈10.1007/978-3-319-28678-5_8〉. 〈hal-01446266〉

Partager

Métriques

Consultations de la notice

31