Faster Fréchet Distance Approximation through Truncated Smoothing

The Fréchet distance is a commonly used distance measure for curves. Computing the Fréchet distance between two polygonal curves of $n$ vertices takes roughly quadratic time, and conditional lower bounds suggest that approximating to within a factor $3$ cannot be done in strongly-subquadratic time, even in one dimension. Currently, the best approximation algorithms present trade-offs between approximation quality and running time. At SoCG 2021, Colombe and Fox presented an $O((n^3\mathrm{/}{\alpha }^2)\log n)$-time $\alpha$-approximate algorithm for curves in arbitrary dimensions, for any $\alpha \in [\sqrt{n},n]$. In this work, we give an $\alpha$-approximate algorithm with a significantly faster running time of $O((n^2\mathrm{/}\alpha )\log n)$, for any $\alpha \in [1,n]$. In particular, we give the first strongly-subquadratic $n^{\epsilon }$-approximation algorithm, for any constant $\epsilon \in (0,1\mathrm{/}2]$. For curves in one dimension we further improve the running time to $O((n^2\mathrm{/}{\alpha }^3){\log }^{2}n)$, for $\alpha \in [1,n^{1\mathrm{/}3}]$. Both of our algorithms rely on a linear-time simplification procedure that in one dimension reduces the complexity of the reachable free space to $O(n^2\mathrm{/}\alpha )$ without making sacrifices in the asymptotic approximation factor.