FD and Approximation GED algorithm

We release an approximation Geometric Edit Distance (GED) algorithm.

Approximation Geometric Edit Distance Algorithm

The Geometric Edit Distance (GED) is one of the well-known similarity metrics between two curves. It can be handled as the special case of the (string) edit distance. The GED for two curves $P$ and $Q$ is defined as the minimum sum of the distance between the matched points of $P$ and $Q$. For the matching, we allow some unmatched points with the penalty cost. Formally, $GED(P,Q)=min_{M \in \mathcal M}{ \sum_{(i,j)\in M} d(P(i),Q(j)) + |\Gamma(M)| }$, where $\mathcal M$ is the set of all possible matching, $\Gamma(M)$ is the set of unmatched points of a matching $M$, and $d(\cdot, \cdot)$ is the distance function.
We implement $\sqrt n$-approximation GED algorithm, where $n$ is the length of the given curves. Our implementation is based on the work of [Fox and Li 22].

Full Changelog: v1.0.0...v2.0.0

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.