A Subquadratic $n^{\epsilon }$-approximation for the Continuous Fréchet Distance

Abstract

The Fréchet distance is a commonly used similarity measure between curves. It is known how to compute the continuous Fréchet distance between two polylines with $m$ and $n$ vertices in ${\mathbb{R}}^d$ in $O(mn(\log \log n{)}^2)$ time; doing so in strongly subquadratic time is a longstanding open problem. Recent conditional lower bounds suggest that it is unlikely that a strongly subquadratic algorithm exists. Moreover, it is unlikely that we can approximate the Fréchet distance to within a factor $3$ in strongly subquadratic time, even if $d=1$. The best current results establish a tradeoff between approximation quality and running time. Specifically, Colombe and Fox (SoCG, 2021) give an $O(\alpha )$-approximate algorithm that runs in $O((n^3/{\alpha }^2)\log n)$ time for any $\alpha \in [\sqrt{n},n]$, assuming $m=n$. In this paper, we improve this result with an $O(\alpha )$-approximate algorithm that runs in $O((n+mn/\alpha ){\log }^{3}n)$ time for any $\alpha \in [1,n]$, assuming $m\le n$ and constant dimension $d$.

20 pages, 5 figures