Approximating Dynamic Time Warping and Edit Distance for a Pair of Point Sequences

Pankaj K. Agarwal, Kyle Fox, Jiangwei Pan +1

We give the first subquadratic-time approximation schemes for dynamic time warping (DTW) and edit distance (ED) of several natural families of point sequences in ${\mathbb{R}}^d$, fo…