2026-08-10T11:21:34Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6048 2024-03-06T10:37:31Z ddc:004 open_access

Approximating the Integral Fréchet Distance Maheshwari, Anil Sack, Jörg-Rüdiger Scheffer, Christian Fréchet distance partial Fréchet similarity curve matching We present a pseudo-polynomial time (1 + epsilon)-approximation algorithm for computing the integral and average Fréchet distance between two given polygonal curves T_1 and T_2. The running time is in O(zeta^{4}n^4/epsilon^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. 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Anil Maheshwari and Jörg-Rüdiger Sack and Christian Scheffer 2016 Is Part Of LIPIcs, Volume 53, 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SWAT.2016.26 urn:nbn:de:0030-drops-60485 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2016.26 eng https://creativecommons.org/licenses/by/3.0/legalcode