A Constant-Factor Approximation for Continuous Dynamic Time Warping in 2D
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913097558523904 |
|---|---|
| author | Buchin, Kevin Buchin, Maike Swiadek, Jan Erik Wong, Sampson |
| author_facet | Buchin, Kevin Buchin, Maike Swiadek, Jan Erik Wong, Sampson |
| contents | Continuous Dynamic Time Warping (CDTW) is a robust similarity measure for polygonal curves that has recently found a variety of applications. Despite its practical use, not much is known about the algorithmic complexity of computing it in 2D, especially when one requires either an exact solution or strong approximation guarantees. We fill this gap by introducing a $5$-approximation algorithm with running time $O(n^5)$ under the 1-norm.
This is the first constant-factor approximation for 2D CDTW with polynomial running time. We extend our algorithm to all polygonal norms on $\mathbb{R}^2$, which we subsequently use in order to achieve a $(5+\varepsilon)$-approximation with time complexity $O(n^5 / \varepsilon^{1/2})$ for CDTW in 2D under any fixed norm. The latter result in particular includes the usual Euclidean 2-norm. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_05917 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | A Constant-Factor Approximation for Continuous Dynamic Time Warping in 2D Buchin, Kevin Buchin, Maike Swiadek, Jan Erik Wong, Sampson Computational Geometry Continuous Dynamic Time Warping (CDTW) is a robust similarity measure for polygonal curves that has recently found a variety of applications. Despite its practical use, not much is known about the algorithmic complexity of computing it in 2D, especially when one requires either an exact solution or strong approximation guarantees. We fill this gap by introducing a $5$-approximation algorithm with running time $O(n^5)$ under the 1-norm. This is the first constant-factor approximation for 2D CDTW with polynomial running time. We extend our algorithm to all polygonal norms on $\mathbb{R}^2$, which we subsequently use in order to achieve a $(5+\varepsilon)$-approximation with time complexity $O(n^5 / \varepsilon^{1/2})$ for CDTW in 2D under any fixed norm. The latter result in particular includes the usual Euclidean 2-norm. |
| title | A Constant-Factor Approximation for Continuous Dynamic Time Warping in 2D |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2605.05917 |