Near-tight Bounds for Computing the Fréchet Distance in d-Dimensional Grid Graphs and the Implications for λ-low Dense Curves

The Fréchet distance is a popular distance measure between trajectories or curves in space, or between walks in graphs. We study computing the Fréchet distance between walks in the $d$-dimensional grid graphs, i.e. ${\mathbb{Z}}^d$ where points share an edge if they differ by one in one coordinate. We give an algorithm, that for two simple paths on $n$ vertices, $(1+\epsilon )$-approximates the Fréchet distance in time $\tilde{O}((\frac{n}{\epsilon }{)}^{2-2\mathrm{/}d}+n)$. We complement this by a near-matching fine-grained lower bound: for constant dimensions $d\ge 3$, there is no $O(({\epsilon }^{2\mathrm{/}d}(\frac{n}{\epsilon }{)}^{2-2\mathrm{/}d}{)}^{1-\delta })$ algorithm for any $\delta >0$ unless the Orthogonal Vector Hypothesis fails. Thus, our results are tight up to a factor ${\epsilon }^{2\mathrm{/}d}$ and $\log (n)$-factors. We extend our results to imbalanced lower and upper bounds, where the curves have $n$ and $m$ vertices respectively, and also obtain near-tight bounds. Driemel, Har-Peled and Wenk [DCG’12] studied \emph{realistic assumptions} for curves to speed up Fréchet distance computation. One of these assumptions is $\lambda$-low density and they can compute a $(1+\epsilon )$-approximation between $\lambda$-low dense curves in time $\tilde{O}({\epsilon }^{-2}{\lambda }^2{n}^{2(1-1\mathrm{/}d)})$. By adapting our lower bound, we show that their algorithm has a tight dependency on $n$ and a tight dependency on $\epsilon$ as $d$ goes to infinity. A gap remains in terms of $\lambda$.