We present a pseudo-polynomial time (1+ε)-approximation algorithm for computing the integral Fréchet distance between two given polygonal curves T1 and T2. The running time is in O(ζ4n4ε2log ζnε) where n is the complexity of T1 and T2 and ζ is the maximal ratio of the lengths of any pair of segments from T1 and T2. This leads to a polynomial running time w.r.t. n and 1ε for ζ O(1).Furthermore, we relate weighted shortest paths inside a parameter cell C to the monotone free space axis of C. As a result we present a simple construction of weighted shortest paths inside a parameter cell. Additionally, such a shortest path provides an optimal solution for the partial Fréchet similarity of segments for all leash lengths. These two aspects are related to each other and are of independent interest.

Additional Metadata
Keywords Curve matching, Fréchet distance, Partial Fréchet similarity
Persistent URL dx.doi.org/10.1016/j.comgeo.2018.01.001
Journal Computational Geometry
Maheshwari, A, Sack, J.-R. (Jörg-Rüdiger), & Scheffer, C. (Christian). (2018). Approximating the integral Fréchet distance. Computational Geometry. doi:10.1016/j.comgeo.2018.01.001