Karl Bringmann

Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping

2015 · arXiv (Cornell University)

Classic similarity measures of strings are longest common subsequence and Levenshtein distance (i.e., the classic edit distance). A classic similarity measure of curves is dynamic time warping. These measures can be computed by simple $O(n^2)$ …