DROPS

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2026.47

A Constant-Factor Approximation for Continuous Dynamic Time Warping in 2D

Authors: Kevin Buchin, Maike Buchin, Jan Erik Swiadek, and Sampson Wong

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract

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⁵) 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 ℝ², which we subsequently use in order to achieve a (5+ε)-approximation with time complexity O(n⁵/ε^{1/2}) for CDTW in 2D under any fixed norm. The latter result in particular includes the usual Euclidean 2-norm.

Cite as

Kevin Buchin, Maike Buchin, Jan Erik Swiadek, and Sampson Wong. A Constant-Factor Approximation for Continuous Dynamic Time Warping in 2D. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 47:1-47:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{buchin_et_al:LIPIcs.ICALP.2026.47,
  author =	{Buchin, Kevin and Buchin, Maike and Swiadek, Jan Erik and Wong, Sampson},
  title =	{{A Constant-Factor Approximation for Continuous Dynamic Time Warping in 2D}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{47:1--47:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.47},
  URN =		{urn:nbn:de:0030-drops-264365},
  doi =		{10.4230/LIPIcs.ICALP.2026.47},
  annote =	{Keywords: Continuous Dynamic Time Warping, Curve Similarity, Geometric Approximation Algorithm}
}

Search Results

Documents authored by Swiadek, Jan Erik

A Constant-Factor Approximation for Continuous Dynamic Time Warping in 2D

Abstract

Cite as

Thanks for your feedback!

Could not send message