Fundamentals of Computing Continuous Dynamic Time Warping in 2D under Different Norms

2025/11/25 by Buchin, Kevin, Buchin, Maike, Swiadek, Jan Erik +1
Computer Science · Decision Sciences · #Time Series Analysis and Forecasting #Data Quality and Management #Data Visualization and Analytics

paper · doi:10.48550/arxiv.2511.20420

Abstract

Continuous Dynamic Time Warping (CDTW) measures the similarity of polygonal curves robustly to outliers and to sampling rates, but the design and analysis of CDTW algorithms face multiple challenges. We show that CDTW cannot be computed exactly under the Euclidean 2-norm using only algebraic operations, and we give an exact algorithm for CDTW under norms approximating the 2-norm. The latter result relies on technical fundamentals that we establish, and which generalise to any norm and to related measures such as the partial Fréchet similarity.

Citations

• Fréchet Distance in Subquadratic Time
• The Fréchet Distance Unleashed: Approximating a Dog with a Frog
• Computing Continuous Dynamic Time Warping of Time Series in Polynomial Time
• Approximating the Integral Fréchet Distance
• A Note on the Unsolvability of the Weighted Region Shortest Path Problem
• Similarity of Polygonal Curves in the Presence of Outliers
• Выпуклая оптимизация

Related

• Computing Continuous Dynamic Time Warping of Time Series in Polynomial Time
• Computing continuous dynamic time warping of time series in polynomial time
• Dynamic Time Warping Under Translation: Approximation Guided by Space-Filling Curves
• Dynamic time warping under translation: Approximation guided by space-filling curves
• Dynamic Dynamic Time Warping