2015/12/10 by Anil Maheshwari, Jörg-Rüdiger Sack, Maheshwari, Anil +3 · 1 citation
Computer Science · #Computational Geometry (cs.CG) #F.2.2 #FOS: Computer and information sciences #cs.CG #msc:F.2.2
paper · pdf · doi:10.48550/arxiv.1512.03359
arxiv created 2015/12/10 · arxiv updated 2015/12/11
A pseudo-polynomial time (1 + ε)-approximation algorithm is presented for computing the integral and average Fréchet distance between two given polygonal curves T1 and T2. In particular, the running time is upper-bounded by 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. The Fréchet distance captures the minimal cost of a continuous deformation of T1 into T2 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 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.