Constant Approximation of Fréchet Distance in Strongly Subquadratic Time

Abstract

Let $\tau$ and $\sigma$ be two polygonal curves in ${\mathbb{R}}^d$ for any fixed $d$. Suppose that $\tau$ and $\sigma$ have $n$ and $m$ vertices, respectively, and $m\le n$. While conditional lower bounds prevent approximating the Fréchet distance between $\tau$ and $\sigma$ within a factor of 3 in strongly subquadratic time, the current best approximation algorithm attains a ratio of $n^c$ in strongly subquadratic time, for some constant $c\in (0,1)$. We present a randomized algorithm with running time $O(n{m}^{0.99}\log (n/\epsilon ))$ that approximates the Fréchet distance within a factor of $7+\epsilon$, with a success probability at least $1-1/n^6$. We also adapt our techniques to develop a randomized algorithm that approximates the \emph{discrete} Fréchet distance within a factor of $7+\epsilon$ in strongly subquadratic time. They are the first algorithms to approximate the Fréchet distance and the discrete Fréchet distance within constant factors in strongly subquadratic time.

To appear at STOC 2025