Exact Fréchet Distance algorithm

We release an exact (continuous) Fréchet Distance (FD) algorithm.

Fréchet Distance Algorithm

The Fréchet Distance (FD) is one of the most well-known similarity metrics between two (polygonal) curves. It is often described metaphorically as the minimum length of a leash required for a person to walk a dog along two separate paths, where the person walks along one curve and the dog along the other.
Formally, The FD for two polygonal curves $P$ and $Q$ is defined as the infimum over all reparameterizations $\alpha$ and $\beta$ of $[0,1]$ of the maximum over all $t\in [0,1]$ of the distance between $P(\alpha(t)$ and $Q(\beta(t)$, i.e., $FD(P,Q)=\text{inf}{\alpha, \beta}\text{max}{t\in [0,1]}{ d(P(\alpha(t)),Q(\beta(t)) }$, where $d(\cdot, \cdot)$ is the distance function.
Our implementation is based on the work of [Alt and Godau 95]. In particular, we implement the non-parallel version of Alt and Godau's. By the work, we implement the decision version and the optimization version of the algorithm.