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

DOI10.4230/LIPICS.SOCG.2016.6zbMath1387.68226arXiv1512.01876OpenAlexW2963393865MaRDI QIDQ3132838

Rex Ying, Jiangwei Pan, Kyle Fox, Pankaj K. Agarwal

Publication date: 30 January 2018

Full work available at URL: https://arxiv.org/abs/1512.01876

zbMATH Keywords

dynamic programmingdynamic time warpingedit distancewell-separated pair decompositionnear-linear-time algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items (2)

Approximating the geometric edit distance ⋮ Dynamic Time Warping in Strongly Subquadratic Time: Algorithms for the Low-Distance Regime and Approximate Evaluation

This page was built for publication: Approximating Dynamic Time Warping and Edit Distance for a Pair of Point Sequences