Metraipolis › archive › dc_2e33abbbccc8

Approximating CDTW Distance of Piecewise Algebraic Curves — arXiv:2609.04294

Source: arXiv (en)
Original: https://arxiv.org/abs/2609.04294
License (as archived): CC0-1.0
Archived: 2026-10-16T23:13:12.694Z
SHA-256 of the archived text: f27057c34182767d3feca4fc66728c52a95af15249da45dcb398a3796f33031b
Stable URL of this page: https://metraipolis.com/documento/dc_2e33abbbccc8

How to cite

Approximating CDTW Distance of Piecewise Algebraic Curves — arXiv:2609.04294 — arXiv (en), https://arxiv.org/abs/2609.04294 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_2e33abbbccc8 (Metraipolis archive dc_2e33abbbccc8, sha256 f27057c34182767d3feca4fc66728c52a95af15249da45dcb398a3796f33031b)

BibTeX

@misc{dc2e33abbbccc8,
  title = {Approximating CDTW Distance of Piecewise Algebraic Curves — arXiv:2609.04294},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.04294},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_2e33abbbccc8; sha256 f27057c34182767d3feca4fc66728c52a95af15249da45dcb398a3796f33031b},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.04294. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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 $\varepsilon$, with $O \left( (m+n)^{\frac{19}{6}} (\frac{1}{\varepsilon})^{\frac{10}{3}} \log \left( \frac{ (m+n) }{\varepsilon^2} \right) \right)$ complexity, where $m$ and $n$ are the number of pieces of the two input curves.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-07 in math.OC).
Categorie arXiv: Computational Geometry (cs.CG) ; Symbolic Computation (cs.SC); Optimization and Control (math.OC).
Pagina del lavoro: https://arxiv.org/abs/2609.04294 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T22:51:59.428Z dalla pagina https://arxiv.org/catchup/math.OC/2026-09-07?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).