Adaptive computation of the discrete Fréchet distance
Author
dc.contributor.author
Barbay, Jérémy
Admission date
dc.date.accessioned
2019-05-31T15:21:07Z
Available date
dc.date.available
2019-05-31T15:21:07Z
Publication date
dc.date.issued
2018
Cita de ítem
dc.identifier.citation
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Volumen 11147, 2018, Pages 50–60
Identifier
dc.identifier.issn
16113349
Identifier
dc.identifier.issn
03029743
Identifier
dc.identifier.other
10.1007/978-3-030-00479-8_5
Identifier
dc.identifier.uri
https://repositorio.uchile.cl/handle/2250/169507
Abstract
dc.description.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 + ω).