Adaptive computation of the discrete Fréchet distance

Abstract

The discrete Fréchet distance is a measure of similarity between point sequences which permits to abstract differences of resolution between the two curves, approximating the original Fréchet distance between curves. Such distance between sequences of respective length n and m can be computed in time within O(nm) and space within O(n + m) using classical dynamic programing techniques, a complexity likely to be optimal in the worst case over sequences of similar lenght unless the Strong Exponential Hypothesis is proved incorrect. We propose a parameterized analysis of the computational complexity of the discrete Fréchet distance in fonction of the area of the dynamic program matrix relevant to the computation, measured by its certificate width ω. We prove that the discrete Fréchet distance can be computed in time within ((n + m)ω) and space within O(n + m + ω).