A Strongly-Subquadratic $(3+\varepsilon)$-Approximation for the Fréchet Distance for Paths in Metric Spaces
2026-07-09 • Computational Geometry
Computational Geometry
AI summaryⓘ
The authors study how to quickly estimate the Fréchet distance, a measure of similarity between two paths, which is usually slow to compute exactly. Previous work gave a randomized method with roughly 7 times approximation in fast time, but the authors improve this to a deterministic method achieving about 3 times approximation much faster. Their algorithm nearly matches known theoretical limits on how well the distance can be approximated quickly. They also provide a special case for one-dimensional paths that exactly matches these limits. Their approach works broadly across different metric spaces under mild conditions.
Fréchet distancepolylinesapproximation algorithmstrong exponential time hypothesis (SETH)metric spaceEuclidean spacesubquadratic timefree spacedeterministic algorithmLp norms
Authors
Thijs van der Horst, Tim Ophelders
Abstract
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$.