Fréchet Distance in Subquadratic Time

Siu-Wing Cheng, Haoqiang Huang

Let $m$ and $n$ be the numbers of vertices of two polygonal curves in ${\mathbb{R}}^d$ for any fixed $d$ such that $m\le n$. Since it was known in 1995 how to compute the Fréchet d…