Adaptive computation of the discrete Fréchet distance
Author
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 + ω).
Indexation
Artículo de publicación SCOPUS
Identifier
URI: https://repositorio.uchile.cl/handle/2250/169507
DOI: 10.1007/978-3-030-00479-8_5
ISSN: 16113349
03029743
Quote Item
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Volumen 11147, 2018, Pages 50–60
Collections