A Strongly-Subquadratic $(3+\varepsilon)$-Approximation for the Fréchet Distance for Paths in Metric Spaces
This work significantly improves the approximation factor from 7+ε to 3+ε for the Fréchet distance in Euclidean spaces, providing a nearly optimal algorithm for a fundamental distance measure in computational geometry.
The authors present a deterministic algorithm that computes a (3+ε)-approximation of the Fréchet distance between two polylines in O(n m^{2/3} log n log(1/ε log n)) time, nearly matching the conditional lower bound of factor 3 under SETH. For one-dimensional polylines, they achieve an exact 3-approximation in O(n m^{2/3} log^{5/3} n) time.
The Fréchet distance is a well-studied distance measure for paths in a metric space. It is mostly studied for paths in $d$-dimensional Euclidean space. Here, computing the Fréchet distance between two polylines takes time roughly quadratic in the number of vertices. Assuming the strong exponential time hypothesis (SETH), it cannot be approximated to within a factor less than $3$ in strongly-subquadratic time. Recently, it was shown that for any $\varepsilon>0$, there exists a randomized algorithm that can compute a $(7+\varepsilon)$-approximation in strongly-subquadratic expected time [Cheng, Huang, and Zhang; STOC'25]. For polylines with $n$ and $m$ vertices in a Euclidean space of constant dimension, where $n \geq m$, their algorithm takes $O(nm^{0.99} \log(n/\varepsilon))$ time in expectation. We present a deterministic approximation algorithm that significantly improves upon the approximation factor and running time. Specifically, our algorithm computes a $(3+\varepsilon)$-approximation in $O(nm^{2/3} \log n \cdot \log (\frac{1}{\varepsilon} \log n))$ time. Our algorithm nearly matches the conditional lower bound on the approximation factor implied by SETH. For polylines in $\mathbb{R}$, we present a $3$-approximation algorithm that runs in $O(nm^{2/3} \log^{5/3} n)$ time, and exactly matches the conditional lower bound. For our results, we introduce a general strongly-subquadratic time $3$-approximate decision algorithm. This algorithm makes no assumptions on the ambient metric space, and relies only on standard assumptions on the so-called free space of the input paths. Under some mild assumptions, our decision algorithm leads to a $(3+\varepsilon)$-approximation algorithm in general metric spaces. These assumptions hold automatically for polylines in any metric space $(\mathbb{R}^d, L_p)$ with $p \geq 1$.