Approximating the integral Fréchet distance
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.
|Keywords||Curve matching, Fréchet distance, Partial Fréchet similarity|
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