$(5+\epsilon )$-Approximation of Fréchet Distance in Strongly Subquadratic Time

Lenny Liu, Jihan Wang

We give randomized $(5+\epsilon )$-approximation algorithms for both the continuous and discrete Fréchet distances on arbitrary two polygonal curves $\tau$ and $\sigma$ in ${\mathbb{R}}^d$ for fixed…