Adaptive Computation of Frechet Distance: Upper and Conditional Lower Bound

Abstract: The Fréchet distance is a measure of similarity between curves that takes into account the location and ordering of the points along the curves, and permits to abstract, among other things, differences of resolution between the two curves (with application to morphing, handwriting recognition and protein structure alignment, among others).

In 1991, Art and Godau introdued this measure to Computational Geometry, describing an algorithm computing the Fréchet distance between two polygonal curves composed of $n$ and $m$ segments respectively in time within $O(mn\log(mn))$, the first algorithm to do so in polynomial time. In 1994, Eiter and Mannila extended the notion of the Fréchet distance between curves to the Fréchet distance between sequence of points of respective sizes $n$ and $m$, demonstrating that the latter cam be computed in time within $O(nm)$ and space within $O(n+m)$, and that it gives a good approximation of the Fréchet distance.

After 20 years without major improvements and no better lower bound than $\Omega(n+m)$, Bringmann decribed in 2014 the first conditional lower bound for the computation of the Discrete Fréchet Distance, via a clever reduction to CNF-SAT, under the Strong Exponential Time Hypothesis (SETH), which yield in turn many similar results for other problems using similar dynamic programming techniques (e.g. DIR Edit Distance).

We propose a refinement of the algorithm and the analysis from Eiter and Mannila to take into account not only the sizes $n$ and $m$ of the point sequences, but also of the difficulty $\omega$ to certify the resulting distance, and the corresponding refinement of the conditional lower bound from Bringmann to take into account this new parameter. It is our hope that such a refinement of the analysis can be (easily?) extended to other problems for which dynamic programming has given good results in the past.

Date: May 09, 2018 at 14:30 h
Venue: Republica 701, Sala 33.
Speaker: Jeremy Barbay
Affiliation: DCC, U. de Chile
Coordinator: Prof. José Verschae
More info at:
Event website

Posted on May 14, 2018 in AGCO, Seminars