%0 Conference Proceedings
%T Minimizing Walking Length in Map Matching
%+ Carleton University
%A Gheibi, Amin
%A Maheshwari, Anil
%A Sack, Jörg-Rüdiger
%< avec comité de lecture
%( Lecture Notes in Computer Science
%B 1st International Conference on Theoretical Computer Science (TTCS)
%C Tehran, Iran
%Y Mohammed Taghi Hajiaghayi
%Y Mohammad Reza Mousavi
%3 Topics in Theoretical Computer Science
%V LNCS-9541
%P 105-120
%8 2015-08-26
%D 2015
%R 10.1007/978-3-319-28678-5_8
%Z Computer Science [cs]Conference papers
%X In 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.
%G English
%Z TC 1
%Z WG 1.8
%2 https://inria.hal.science/hal-01446266/document
%2 https://inria.hal.science/hal-01446266/file/385217_1_En_8_Chapter.pdf
%L hal-01446266
%U https://inria.hal.science/hal-01446266
%~ IFIP-LNCS
%~ IFIP
%~ IFIP-TC
%~ IFIP-TC1
%~ IFIP-LNCS-9541
%~ IFIP-WG1-8
%~ IFIP-TTCS