I will discuss the approximability of the discrete Fréchet distance. Building on a recent result by Bringmann, I will present a new conditional lower bound showing that strongly subquadratic algorithms for the discrete Fréchet distance are unlikely to exist, even in the one-dimensional case and even if the solution may be approximated up to a factor of, say, 1.399.

This raises the question of how well we can approximate the Fréchet distance in strongly subquadratic time. Previously, no general results were known. I will show the first such algorithm by analyzing the approximation ratio of a simple, linear-time greedy algorithm to be $2^{\Theta(n)}$. Moreover, I will sketch an $\alpha$-approximation algorithm that runs in time $O(n \log n + n^2/\alpha)$, for any $\alpha$ in $[1, n]$. Hence, an $n^ɛ$-approximation of the Fréchet distance can be computed in strongly subquadratic time, for any $ɛ > 0$.

Joint work with Karl Bringmann.