Approximating the Integral Fréchet Distance

الأصل · EN

A pseudo-polynomial time (1 + ε)-approximation algorithm is presented for computing the integral and average Fréchet distance between two given polygonal curves T₁ and T₂. In particular, the running time is upper-bounded by O(ζ⁴n⁴/ε²) where n is the complexity of T₁ and T₂ and ζ is the maximal ratio of the lengths of any pair of segments from T₁ and T₂. The Fréchet distance captures the minimal cost of a continuous deformation of T₁ into T₂ and vice versa and defines the cost of a deformation as the maximal distance between two points that are related. The integral Fréchet distance defines the cost of a deformation as the integral of the distances between points that are related. The average Fréchet distance is defined as the integral Fréchet distance divided by the lengths of T₁ and T₂. 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.