We present a pseudo-polynomial time (1+ε)-approximation algorithm for computing the integral and average Fréchet distance between two given polygonal curves T1 and T2. The running time is in O(ζ4n4/ε2) 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. Furthermore, we give relations between weighted shortest paths inside a single parameter cell C and 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.4230/LIPIcs.SWAT.2016.26
Conference 15th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2016
Citation
Maheshwari, A, Sack, J.-R, & Scheffer, C. (Christian). (2016). Approximating the integral Fréchet distance. In Leibniz International Proceedings in Informatics, LIPIcs (pp. 26.1–26.14). doi:10.4230/LIPIcs.SWAT.2016.26