Approximating CDTW Distance of Piecewise Algebraic Curves
Abstract
Curves as input data naturally arise in a variety of fields including finance, seismology, medicine, spatio-temporal data mining, malicious activity detection, and more. A common way to analyze these data sets is to do similarity matching or clustering. The most common metrics used for measuring similarity of curves are Dynamic Time Warping (DTW) and Fréchet distance. These metrics are sensitive to sampling rate and outliers respectively, and do not yield robust outcomes. Continuous Dynamic Time Warping (CDTW) is a more robust distance metric that improves upon DTW and Fréchet distances. Existing algorithms for CDTW are either exact algorithms that focus on non-Euclidean norms and piecewise linear curves, or approximation algorithms limited to piecewise linear curves. We present an approximation algorithm for computing the CDTW distance under Euclidean norm between piecewise (higher degree) algebraic curves. That is, we present a fully polynomial-time approximation scheme (FPTAS) of multiplicative error ε, with O ( (m+n)19/6 (1/ε)10/3 log ( ( (m+n) )/ε2 ) ) complexity, where m and n are the number of pieces of the two input curves.
Related
- Cutting a convex body into fat parts and approximating Euclidean distance by graph distances
- Maximality and configuration spaces on real algebraic curves
- Triple intersections for algebraic curves on the real torus
- MDS Algebraic Geometry Codes of Square-Root Length on Hyperelliptic Curves
- Likely and unlikely ramification of algebraic points on curves
BibTeX
@misc{ergur2026approximating,
title = {{Approximating CDTW Distance of Piecewise Algebraic Curves}},
author = {Alperen A. Ergür and Shamik Khowala},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.04294},
eprint = {2609.04294},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.04294},
}
RIS
TY - UNPB
TI - Approximating CDTW Distance of Piecewise Algebraic Curves
AU - Alperen A. Ergür
AU - Shamik Khowala
PY - 2026
DA - 2026/09/03
PB - arXiv
DO - 10.48550/arxiv.2609.04294
UR - https://arxiv.org/abs/2609.04294
AB - Curves as input data naturally arise in a variety of fields including finance, seismology, medicine, spatio-temporal data mining, malicious activity detection, and more. A common way to analyze these data sets is to do similarity matching or clustering. The most common metrics used for measuring similarity of curves are Dynamic Time Warping (DTW) and Fréchet distance. These metrics are sensitive to sampling rate and outliers respectively, and do not yield robust outcomes. Continuous Dynamic Time Warping (CDTW) is a more robust distance metric that improves upon DTW and Fréchet distances. Existing algorithms for CDTW are either exact algorithms that focus on non-Euclidean norms and piecewise linear curves, or approximation algorithms limited to piecewise linear curves. We present an approximation algorithm for computing the CDTW distance under Euclidean norm between piecewise (higher degree) algebraic curves. That is, we present a fully polynomial-time approximation scheme (FPTAS) of multiplicative error ε, with O ( (m+n)^19/6 (1/ε)^10/3 log ( ( (m+n) )/ε^2 ) ) complexity, where m and n are the number of pieces of the two input curves.
ER -