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
