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