Approximating the integral Fréchet distance
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.
|Keywords||Curve matching, Fréchet distance, Partial Fréchet similarity|
|Conference||15th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2016|
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