Approximating the Fréchet Distance in Graphswith Low Highway Dimension

In this paper, we study algorithms for the discrete Fréchet distance in graphs with low highway dimension. We describe a $(5sqrt{3} + varepsilon)$-approximation algorithm for the Fréchet distance between a shortest path $P$ with $n$ vertices and an arbitrary walk $Q$ with $m$ vertices in a graph $G = (V, E)$. The algorithm makes use of a collection of sparse shortest paths hitting sets which are precomputed for the graph $G$. After preprocessing, the algorithm has running time $Oleft(n log D + m(h log h log D)^2right)$, where $h$ is the highway dimension and $D$ is the diameter of $G$. The preprocessing for the graph is polynomial in $lvert G rvert$ and $1 / log(1 + varepsilon)$ and uses $Oleft(lvert V rvert log D left(1 / log(1 + varepsilon) + h log hright)right)$ space.