https://hal.inria.fr/hal-01446266Gheibi, AminAminGheibiCarleton UniversityMaheshwari, AnilAnilMaheshwariCarleton UniversitySack, Jörg-RüdigerJörg-RüdigerSackCarleton UniversityMinimizing Walking Length in Map MatchingHAL CCSD2016[INFO] Computer Science [cs]Ifip, HalMohammed Taghi HajiaghayiMohammad Reza Mousavi2017-01-25 16:51:012017-01-26 09:30:232017-01-26 09:30:23enConference papershttps://hal.inria.fr/hal-01446266/document10.1007/978-3-319-28678-5_8application/pdf1In this paper, we propose a geometric algorithm for a map matching problem. More specifically, we are given a planar graph, <i>H</i>, with a straight-line embedding in a plane, a directed polygonal curve, <i>T</i>, and a distance value $\varepsilon >0$. The task is to find a path, <i>P</i>, in <i>H</i>, and a parameterization of <i>T</i>, that minimize the sum of the length of walks on <i>T</i> and <i>P</i> whereby the distance between the entities moving along <i>P</i> and <i>T</i> is at most $\varepsilon$ε, at any time during the walks. It is allowed to walk forwards and backwards on <i>T</i> and edges of <i>H</i>. 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 <i>m</i> (<i>n</i>, respectively) is the number of edges of <i>H</i> (of <i>T</i>, respectively). As we show, the algorithm can be generalized to work also for weighted non-planar graphs within the same time and space complexities.