arxiv: 2605.05917 · v1 · submitted 2026-05-07 · 💻 cs.CG

Recognition: unknown

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

Jan Erik Swiadek, Kevin Buchin, Maike Buchin, Sampson Wong

Authors on Pith no claims yet

Pith reviewed 2026-05-08 03:22 UTC · model grok-4.3

classification 💻 cs.CG

keywords continuous dynamic time warpingapproximation algorithmspolygonal curves2D geometrydynamic programmingnormscomputational geometry

0 comments

The pith

A polynomial-time algorithm approximates continuous dynamic time warping between 2D curves within a factor of 5.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper presents an algorithm that computes a 5-approximation of the continuous dynamic time warping distance for polygonal curves in the plane under the 1-norm. This is achieved in O(n^5) time, which is polynomial. The approach extends to a (5 + epsilon)-approximation for any fixed norm with slightly higher time complexity. If correct, this allows efficient computation of a robust similarity measure for curves without requiring exponential time or losing constant-factor guarantees.

Core claim

We introduce a 5-approximation algorithm with running time O(n^5) for continuous dynamic time warping of polygonal curves in 2D under the 1-norm. This is the first constant-factor approximation for 2D CDTW with polynomial running time. We extend the method to all polygonal norms and use it to obtain a (5 + ε)-approximation in O(n^5 / ε^{1/2}) time for CDTW under any fixed norm, including the Euclidean 2-norm.

What carries the argument

A dynamic programming approach that discretizes the continuous warping path for polygonal curves, bounding the approximation error by a factor of 5 under the 1-norm.

Load-bearing premise

The dynamic programming table correctly computes a value within factor 5 of the true continuous minimum warping cost for any pair of polygonal curves.

What would settle it

A pair of simple polygonal curves in 2D where the algorithm's output exceeds 5 times the true CDTW distance.

Figures

Figures reproduced from arXiv: 2605.05917 by Jan Erik Swiadek, Kevin Buchin, Maike Buchin, Sampson Wong.

**Figure 1.** Figure 1: Optimal paths from different cells’ south borders to their output borders Note that Theorem 4 relies on the usage of norms in Definition 1: The equipped norm ∥ · ∥ measures both distances between curve points and speeds of curve parametrisations [5], while the 1-norm ∥ · ∥1 combines these speeds within the CDTW path integral [8,16,7,2,5]. Moreover, Theorem 4 only holds in 1D and 2D. See Appendix B for a 3D… view at source ↗

**Figure 2.** Figure 2: Approximable paths and their corresponding curve matchings Our technical proof of the following lemma relies – similar to Theorem 4 – on Definition 1 and Definition 3 employing the equipped norm ∥ · ∥ for distances between curve points as well as speeds and arc lengths on each curve. In particular, this allows for a versatile use of the triangle inequality and symmetry of the metric (p, q) 7→ ∥p − q∥ induc… view at source ↗

**Figure 3.** Figure 3: Example of algorithm steps in case of min HS = h ∗ S < h∗ W = min HW In a final step, at most one input border A is propagated to its opposing output border B, namely if its best path to the north-east corner is better than the other one. The subroutine B.PropagateFromOpposing updates B.apx by computing a lower envelope over all points located on A up to its best path’s starting point. See Figure 3d for an… view at source ↗

**Figure 4.** Figure 4: Different configurations yielding a path with at worst approximating cost Proposition 13. Let B be an output border of a cell C with adjoining input border A := B.adj. We have B.apx(t) ≤ A.apx(s) + 5 · optA,B(s, t) for all (s, t) ∈ dom(A) × dom(B). Proof. Let γ be an optimal (A(s), B(t))-path as in Theorem 4. Assume first that γ is of the form from Theorem 4a. This implies that γ intersects all paths from … view at source ↗

**Figure 5.** Figure 5: Local minima of a continuous and piecewise quadratic function Overall, there are O(NC.S + NC.W) parent candidates for the north-east corner of C. We can check all of them to find starting points of best paths, as the global minima that exist by Lemma 11 are among the local minima. Thus, computing the required values from lines 10–11 of Algorithm 1 takes O(NC.S + NC.W) time under ∥ · ∥1. Moreover, we can re… view at source ↗

**Figure 6.** Figure 6: Intersection between piecewise quadratic functions A(s ∗ ) S1 S2 S3 S4 S5 T1 T3 T5 view at source ↗

**Figure 8.** Figure 8: Polygons whose gauges are norms, along with evaluation vectors for specific cones view at source ↗

**Figure 9.** Figure 9: Behaviour of a continuous lower envelope depending on the functions’ derivatives It remains to bound the number of semistrict local minima with derivative 0 occurring on I. For this, we count the distinct (a, b)-coefficient pairs over all the quadratic pieces s 7→ as2 +bs+c of the function A.apx on I. Such a pair determines the derivative of the pieces to be s 7→ 2as + b, and thereby fixes the the sole poi… view at source ↗

**Figure 10.** Figure 10: Parameter space cell of curve segments in (R 3 , ∥ · ∥1) without a genuine valley It is not clear whether it is possible to extend our results to this kind of setting. One approach might be to subdivide the cell into parts such that every part has a valley. However, these parts would not be rectangles anymore since we would need to use lines of slope −1 for the subdivision. This could complicate propagati… view at source ↗

read the original 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^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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper gives the first constant-factor polynomial-time approximation for 2D continuous DTW on polygonal curves, a 5-approx in O(n^5) under L1 that extends to (5+ε) for any fixed norm.

read the letter

The main advance is a dynamic program over pairs of segments that tracks alignment parameters and uses L1 separability together with the triangle inequality to charge any continuous optimal matching to a discrete path whose cost is at most 5 times larger. The argument holds for general, possibly self-intersecting curves and requires no extra simplicity assumptions. That is genuinely new; prior work left open whether a constant-factor poly-time result even existed for 2D CDTW. The extension to arbitrary norms by approximating the unit ball and paying an extra 1/sqrt(ε) factor in the running time is a clean follow-on that covers the Euclidean case as well. The construction is explicit and the error analysis is built directly from the recurrence, so the central claim looks reproducible once the full details are checked. The obvious soft spot is the O(n^5) degree, which is polynomial but high enough that the algorithm will only be practical for modest n unless further speed-ups appear. The ε-dependence in the general-norm version is also not optimal, though it is not a load-bearing flaw. For readers working on curve similarity measures or geometric approximation algorithms this is worth reading; it turns an open complexity question into a concrete algorithmic result. I would send it to peer review because the problem is well-motivated, the approach is constructive, and the claimed guarantee is stated clearly enough to be checked.

Referee Report

0 major / 3 minor

Summary. The manuscript presents a 5-approximation algorithm for Continuous Dynamic Time Warping (CDTW) between two polygonal curves in 2D under the L1 norm, running in O(n^5) time. The approach uses dynamic programming over pairs of segments augmented with states for alignment parameters; L1 separability and the triangle inequality are used to charge the cost of any continuous optimal matching to a discrete path whose cost is at most 5 times larger. The result is extended to all polygonal norms and yields a (5 + ε)-approximation under an arbitrary fixed norm in time O(n^5 / ε^{1/2}). The analysis holds for general (possibly self-intersecting) curves.

Significance. If the central DP construction and charging argument are correct, this supplies the first constant-factor polynomial-time approximation for 2D CDTW, addressing a clear gap between the practical use of CDTW and its theoretical complexity. The constructive nature of the algorithm, its generality to self-intersecting curves, and the clean extension to (5 + ε) approximations under any fixed norm are genuine strengths.

minor comments (3)

[§3] §3 (DP recurrence): the precise definition of the alignment-parameter states is given only in text; adding a small diagram or table enumerating the O(1) states per segment pair would improve readability without lengthening the paper.
[§4] §4 (error analysis): the factor-5 charging argument is stated for the L1 case, but the transition to the (5 + ε) result for general norms via polygonal-norm approximation is only sketched; a single sentence clarifying the dependence of the hidden constant on the norm would remove ambiguity.
[Abstract] Abstract and §1: the input size parameter n is used without explicit statement that each curve has Θ(n) vertices; a parenthetical clarification would prevent minor confusion for readers outside computational geometry.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary, significance assessment, and recommendation of minor revision. We are pleased that the novelty of the first constant-factor polynomial-time approximation for 2D CDTW, the generality to self-intersecting curves, and the clean extension to (5 + ε) approximations under arbitrary fixed norms were recognized.

Circularity Check

0 steps flagged

No significant circularity; constructive DP approximation with independent analysis

full rationale

The manuscript constructs a dynamic programming algorithm over segment pairs with auxiliary states for alignment parameters, then proves the 5-approximation bound by charging any continuous optimum to a discrete feasible path via the triangle inequality and L1 separability. These charging arguments rely on standard metric properties that hold for arbitrary polygonal curves and are independent of the algorithm's recurrence or the target result. No fitted parameters, self-definitional equations, or load-bearing self-citations appear in the derivation chain. The result is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The result rests on standard properties of norms and polygonal curves; no free parameters, new entities, or ad-hoc axioms are introduced in the abstract.

axioms (1)

domain assumption Polygonal curves in R^2 and standard norm properties allow discretization without loss of the approximation guarantee.
Invoked to justify the O(n^5) dynamic programming approach.

pith-pipeline@v0.9.0 · 5460 in / 1181 out tokens · 55352 ms · 2026-05-08T03:22:16.716140+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

23 extracted references · 19 canonical work pages · 1 internal anchor

[1]

On map-matching vehicle tracking data

Sotiris Brakatsoulas, Dieter Pfoser, Randall Salas, and Carola Wenk. On map-matching vehicle tracking data. InProceedings of the 31st International Conference on Very Large Data Bases, pages 853–864. VLDB Endowment, 2005. URL:https://dl.acm.org/doi/10.5555/1083592.1083691

work page doi:10.5555/1083592.1083691 2005
[2]

PhD thesis, University of Sydney, 2022

Milutin Brankovic.Graphs and Trajectories in Practical Geometric Problems. PhD thesis, University of Sydney, 2022

2022
[3]

(k, l)-medians clustering of trajectories using Continuous Dynamic Time Warping

Milutin Brankovic, Kevin Buchin, Koen Klaren, André Nusser, Aleksandr Popov, and Sampson Wong. (k, l)-medians clustering of trajectories using Continuous Dynamic Time Warping. InProceedings of the 28th International Conference on Advances in Geographic Information Systems, pages 99–110. ACM, 2020.doi:10.1145/3397536.3422245

work page doi:10.1145/3397536.3422245 2020
[4]

Bronstein

Efim M. Bronstein. Approximation of convex sets by polytopes.Journal of Mathematical Sciences, 153(6):727–762, 2008.doi:10.1007/S10958-008-9144-X. 20 K. Buchin, M. Buchin, J. E. Swiadek, S. Wong

work page doi:10.1007/s10958-008-9144-x 2008
[5]

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

Kevin Buchin, Maike Buchin, Jan Erik Swiadek, and Sampson Wong. Fundamentals of computing Continuous Dynamic Time Warping in 2D under different norms. In20th International Conference and Workshops on Algorithms and Computation, pages 467–482. Springer, 2026.arXiv:2511.20420, doi:10.1007/978-981-95-7127-7_31

work page internal anchor Pith review Pith/arXiv arXiv doi:10.1007/978-981-95-7127-7_31 2026
[6]

Exact algorithms for partial curve matching via the Fréchet distance

Kevin Buchin, Maike Buchin, and Yusu Wang. Exact algorithms for partial curve matching via the Fréchet distance. InProceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 645–654. SIAM, 2009.doi:10.1137/1.9781611973068.71

work page doi:10.1137/1.9781611973068.71 2009
[7]

Computing Continuous Dynamic Time Warping of time series in polynomial time.Journal of Computational Geometry, 16(1):765–799, 2025.doi: 10.20382/JOCG.V16I1A21

Kevin Buchin, André Nusser, and Sampson Wong. Computing Continuous Dynamic Time Warping of time series in polynomial time.Journal of Computational Geometry, 16(1):765–799, 2025.doi: 10.20382/JOCG.V16I1A21

work page doi:10.20382/jocg.v16i1a21 2025
[8]

PhDthesis, Freie Universität Berlin, 2007

MaikeBuchin.On the Computability of the Fréchet Distance between Triangulated Surfaces. PhDthesis, Freie Universität Berlin, 2007. URL:https://refubium.fu-berlin.de/handle/fub188/1909

2007
[9]

Unconstrained submodular maximization with constant adaptive complexity , booktitle =

Deeparnab Chakrabarty and Chaitanya Swamy. Approximation algorithms for minimum norm and ordered optimization problems. InProceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 126–137. ACM, 2019.doi:10.1145/3313276.3316322

work page doi:10.1145/3313276.3316322 2019
[10]

New results on a general class of minimum norm optimization problems

Kuowen Chen, Jian Li, Yuval Rabani, and Yiran Zhang. New results on a general class of minimum norm optimization problems. In52nd International Colloquium on Automata, Languages, and Programming, pages 50:1–50:20. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025.doi: 10.4230/LIPICS.ICALP.2025.50

work page doi:10.4230/lipics.icalp.2025.50 2025
[11]

Alon Efrat, Quanfu Fan, and Suresh Venkatasubramanian. Curve matching, time warping, and light fields: New algorithms for computing similarity between curves.Journal of Mathematical Imaging and Vision, 27(3):203–216, 2007.doi:10.1007/S10851-006-0647-0

work page doi:10.1007/s10851-006-0647-0 2007
[12]

Dynamic Time Warping and Geometric Edit Distance: Breaking the quadratic barrier.ACM Transactions on Algorithms, 14(4):50:1–50:17, 2018

Omer Gold and Micha Sharir. Dynamic Time Warping and Geometric Edit Distance: Breaking the quadratic barrier.ACM Transactions on Algorithms, 14(4):50:1–50:17, 2018. doi:10.1145/3230734

work page doi:10.1145/3230734 2018
[13]

On the generalized Fréchet distance and its applications

Theodor Gutschlag and Sabine Storandt. On the generalized Fréchet distance and its applications. InProceedings of the 30th International Conference on Advances in Geographic Information Systems, pages 35:1–35:10. ACM, 2022.doi:10.1145/3557915.3560970

work page doi:10.1145/3557915.3560970 2022
[14]

Sariel Har-Peled, Benjamin Raichel, and Eliot W. Robson. The Fréchet distance unleashed: Ap- proximating a dog with a frog. In41st International Symposium on Computational Geometry, pages 54:1–54:13. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025.arXiv:2407.03101, doi:10.4230/LIPICS.SOCG.2025.54

work page doi:10.4230/lipics.socg.2025.54 2025
[15]

Continuous Dynamic Time Warping for clustering curves

Koen Klaren. Continuous Dynamic Time Warping for clustering curves. Master’s thesis, Eindhoven University of Technology, 2020. URL:https://research.tue.nl/en/studentTheses/continuou s-dynamic-time-warping-for-clustering-curves

2020
[16]

Approximating the integral Fréchet distance.Computational Geometry, 70–71:13–30, 2018.doi:10.1016/J.COMGEO.2018.01.001

Anil Maheshwari, Jörg-Rüdiger Sack, and Christian Scheffer. Approximating the integral Fréchet distance.Computational Geometry, 70–71:13–30, 2018.doi:10.1016/J.COMGEO.2018.01.001

work page doi:10.1016/j.comgeo.2018.01.001 2018
[17]

Munich and Pietro Perona

Mario E. Munich and Pietro Perona. Continuous Dynamic Time Warping for translation-invariant curve alignment with applications to signature verification. InProceedings of the Seventh IEEE International Conference on Computer Vision, pages 108–115. IEEE, 1999.doi:10.1109/ICCV.199 9.791205

work page doi:10.1109/iccv.199 1999
[18]

Approximating a convex body by a polytope using the Epsilon-Net Theorem

Márton Naszódi. Approximating a convex body by a polytope using the Epsilon-Net Theorem. Discrete & Computational Geometry, 61(3):686–693, 2019.doi:10.1007/S00454-018-9977-0

work page doi:10.1007/s00454-018-9977-0 2019
[19]

Schaefer and Manfred P

Helmut H. Schaefer and Manfred P. Wolff.Topological Vector Spaces. Springer, 2nd edition, 1999. doi:10.1007/978-1-4612-1468-7

work page doi:10.1007/978-1-4612-1468-7 1999
[20]

Subpixel contour matching using continuous dynamic programming

Bruno Serra and Marc Berthod. Subpixel contour matching using continuous dynamic programming. In1994 Proceedings of IEEE Conference on Computer Vision and Pattern Recognition, pages 202–207. IEEE, 1994.doi:10.1109/CVPR.1994.323830

work page doi:10.1109/cvpr.1994.323830 1994
[21]

Optimal subpixel matching of contour chains and segments

Bruno Serra and Marc Berthod. Optimal subpixel matching of contour chains and segments. In Proceedings of IEEE International Conference on Computer Vision, pages 402–407. IEEE, 1995. doi:10.1109/ICCV.1995.466911. A Constant-Factor Approximation for CDTW in 2D 21

work page doi:10.1109/iccv.1995.466911 1995
[22]

A survey of trajectory distance measures and performance evaluation.The VLDB Journal, 29(1):3–32, 2020.doi:10.1007/ S00778-019-00574-9

Han Su, Shuncheng Liu, Bolong Zheng, Xiaofang Zhou, and Kai Zheng. A survey of trajectory distance measures and performance evaluation.The VLDB Journal, 29(1):3–32, 2020.doi:10.1007/ S00778-019-00574-9

2020
[23]

Silveira, Kevin Buchin, Stef Sijben, Ross S

Yaguang Tao, Alan Both, Rodrigo I. Silveira, Kevin Buchin, Stef Sijben, Ross S. Purves, Patrick Laube, Dongliang Peng, Kevin Toohey, and Matt Duckham. A comparative analysis of trajectory similarity measures.GIScience & Remote Sensing, 58(5):643–669, 2021.doi:10.1080/15481603.2 021.1908927. A Proof of Proposition 9 Proposition 9. For every borderB the fun...

work page doi:10.1080/15481603.2 2021