A pseudo-polynomial time $(1 + \varepsilon)$-approximation algorithm is presented for computing the integral and average Fr\'{ e}chet distance between two given polygonal curves $T_1$ and $T_2$. In particular, the running time is upper-bounded by $\mathcal{ O}( \zeta^{ 4}n^4/\varepsilon^{ 2})$ where $n$ is the complexity of $T_1$ and $T_2$ and $\zeta$ is the maximal ratio of the lengths of any pair of segments from $T_1$ and $T_2$. The Fr\'{ e}chet distance captures the minimal cost of a continuous deformation of $T_1$ into $T_2$ and vice versa and defines the cost of a deformation as the maximal distance between two points that are related. The integral Fr\'{ e}chet distance defines the cost of a deformation as the integral of the distances between points that are related. The average Fr\'{ e}chet distance is defined as the integral Fr\'{ e}chet distance divided by the lengths of $T_1$ and $T_2$. 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\'{ e}chet similarity of segments for all leash lengths. These two aspects are related to each other and are of independent interest.
Categories: cs.CG