$(5+\hat{I}\mu )$-Approximation of Fréchet Distance in Strongly Subquadratic Time

Abstract

We give randomized $(5+\hat{I}\mu )$-approximation algorithms for both the continuous and discrete Fréchet distances on arbitrary two polygonal curves $\ddot{I}„$ and $\ddot{I}ƒ$ in ${\mathbb{R}}^d$ for fixed $d$, with $n$ and $m\le n$ vertices respectively. Our algorithm for continuous Fréchet runs in ${\tilde{O}}_{d,\hat{I}\mu }(n{m}^{8/9})$ time, and our algorithm for discrete Fréchet runs in ${\tilde{O}}_{d,\hat{I}\mu }(n{m}^{4/5})$ time. These bounds improve the recent strongly subquadratic constant-factor approximation algorithms of Cheng, Huang, and Zhang~\cite{cheng2025constant}, which give $(7+\hat{I}\mu )$-approximations. The approximation improvement comes from certifying long boundary-to-boundary reachability directly through auxiliary surrogate curves, avoiding an extra conversion back to input subcurves and hence removing one triangle-inequality loss. The running-time improvement comes from a two-scale macro-surrogate search combined with dyadic auxiliary-transfer structures, with the discrete case gaining a faster bound from exact planar reachability in the discrete free-space graph.

Topics & keywords