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

Basic Information

• Paper ID: 2511.20420
• Title: Fundamentals of Computing Continuous Dynamic Time Warping in 2D under Different Norms
• Authors: Kevin Buchin (TU Dortmund), Maike Buchin (Ruhr University Bochum), Jan Erik Swiadek (Ruhr University Bochum), Sampson Wong (University of Copenhagen)
• Classification: cs.CG (Computational Geometry)
• Publication Time/Conference: WALCOM 2026 (preprint version, submitted November 2025)
• Paper Link: https://arxiv.org/abs/2511.20420

Abstract

Continuous Dynamic Time Warping (CDTW) robustly measures the similarity of polygonal curves with resilience to outliers and varying sampling rates. However, the design and analysis of CDTW algorithms face multiple challenges. This paper proves that under the Euclidean 2-norm, CDTW cannot be computed exactly using only algebraic operations, and provides exact algorithms for computing CDTW under norms approximating the 2-norm. The latter relies on technical foundations established by the authors that generalize to arbitrary norms and related metrics (such as partial Fréchet similarity).

Research Background and Motivation

Research Problem

This paper investigates how to efficiently and accurately compute the continuous dynamic time warping (CDTW) distance between polygonal curves in two-dimensional space.

Problem Importance

1. Broad Practical Applications: CDTW has important applications in signature verification, map matching, trajectory clustering, and other domains
2. Overcoming Limitations of Discrete Methods: Traditional discrete DTW ignores the continuity of curves, producing poor results when sampling rates differ or are insufficiently high
3. Robustness Requirements: Compared to the Fréchet distance's sensitivity to outliers through maximum-based metrics, CDTW uses path integration and better handles outliers

Limitations of Existing Methods

1. Approximation and Heuristic Approaches: Many existing methods handle integrals by discretizing input curves, causing solution quality or runtime to depend on discretization resolution
2. Dimensional Constraints: Previous exact algorithms were primarily limited to one-dimensional cases, or only pseudo-polynomial time (1+ε)-approximation algorithms in 2D Euclidean 2-norm
3. Insufficient Theoretical Understanding: Fundamental properties of CDTW, particularly in 2D and under different norms, remain insufficiently understood

Research Motivation

The authors aim to:

1. Deeply understand the computational complexity of CDTW, particularly its non-computability under the 2-norm
2. Establish technical foundations applicable to arbitrary norms
3. Design exact/approximate algorithms that avoid curve discretization

Core Contributions

1. Local Optimality Theory (Section 2): Proves that the path integral-based CDTW definition permits locally optimal matchings advantageous from an algorithmic perspective, and establishes the existence and computation methods of valleys applicable to arbitrary norms
2. Non-Computability Results (Section 3): Proves that under the Euclidean 2-norm, numerical values involved in CDTW may be transcendental numbers, and therefore cannot be computed exactly using only algebraic operations (ACMQ model)
3. Polygonal Norm Algorithm (Section 4): Proposes an exact algorithm for computing CDTW under norms with polygonal level sets, which:
   • Requires no discretization of input curves
   • Can be used to obtain (1+ε)-approximations for the 2-norm
   • Uses regular polygonal norms with k ∈ O(ε^(-1/2))
4. Technical Properties: Establishes multiple technical properties including optimal function continuity and propagation ordering, providing foundations for complexity analysis

Detailed Methodology

Task Definition

Input:

• Two two-dimensional polygonal curves P = ⟨p₀, ..., pₙ⟩ and Q = ⟨q₀, ..., qₘ⟩
• Norm ‖·‖

Output:

• CDTW value cdtw‖·‖(P,Q)

CDTW Definition (Definition 1): $\text{cdtw}_{\|\cdot\|}(P,Q) := \inf_{(f,g)\in\Pi(P)\times\Pi(Q)} \int_0^1 d(f(t), g(t)) \cdot \left\|\begin{pmatrix}\|f'(t)\| \\ \|g'(t)\|\end{pmatrix}\right\|_1 dt$

where:

• Π(P) contains all monotone and piecewise continuously differentiable parameterizations of P
• d(·,·) is the distance function (this paper uses d(p,q) = ‖p-q‖)
• The 1-norm normalizes velocity, making path arc length σ = ‖P‖ + ‖Q‖

Core Technical Framework

1. Parameter Space and Optimal Paths (Section 2)

Parameter Space (Definition 2): 0, ‖P‖ × 0, ‖Q‖, partitioned into n×m cells

Valley Concept (Definition 4):

• A valley ℓ is a line in parameter space (slope ≠ -1)
• Each point z ∈ ℓ is a sink: the function along slope -1 lines achieves its minimum at z

Key Theorem (Theorem 8): For any norm ‖·‖ and polygonal segments P, Q, there exists a valley with positive slope. This is proven through duality and geometric analysis:

• Use Lemma 7 to minimize gauge functions on lines
• Prove existence of maximizing point v* with positive components
• For polygonal norms, compute valleys in O(1) time (Corollary 9)

Optimal Path Characterization (Theorem 5): Given valley ℓ, the optimal (x,y)-path traces as follows:

• If ℓ intersects rectangle Ξ = x₁,y₁×x₂,y₂, the path goes from x to x̂ (on ℓ) to ŷ (on ℓ) to y
• Otherwise, the path goes from x to ξ to y, where ξ is the closest point in Ξ to ℓ

2. Transcendence Results (Section 3)

Main Theorem (Theorem 11): Constructs curves with integer vertices P, Q such that:

• (a) cdtw‖·‖₂(P,Q) is a transcendental number
• (b) The coordinates of every turning point of each optimal path are transcendental numbers

Proof Strategy:

• Construct specific two-segment curve P and three-segment curve Q
• Obtain CDTW values containing logarithmic terms through integral calculation
• Use Baker's theorem (from transcendental number theory, Lemma 10) to prove involved numbers are not algebraic
• For (b), prove that points minimizing derivatives are also transcendental

Significance: This shows that under the 2-norm, CDTW not only cannot be expressed using radicals, but is not even an algebraic number. Therefore, no exact algorithm using algebraic operations can exist.

3. Polygonal Norm Algorithm (Section 4)

Algorithm Framework: Dynamic programming propagating optimal path costs through parameter space cells

Norm Setting:

• Use norm Gψ(Rₖ) whose 1-sublevel set is ψ(Rₖ)
• Rₖ is a regular k-gon (k even) with vertices vᵣ = (cos(θᵣ), sin(θᵣ))ᵀ, θᵣ = r·2π/k
• ψ: ℝ² → ℝ² is a bijective linear map

Key Properties (Lemma 14):

• (a) Gψ(Rₖ) can be evaluated in O(1) time, linear on each cone
• (b) Propagation space ΣA,B can be represented by arrangement of O(k) lines, optA,B is quadratic on each face
• (c) Optimal function opt₀,B is piecewise quadratic

Propagation Process (Algorithm Propagate):

Input: Curve segments P,Q, boundary B, optimal functions for adjacent and opposite edges
Output: Optimal function for B (piecewise quadratic)

1. Compute valley ℓ (O(1) time, Corollary 9)
2. For each boundary A ∈ {adj(B), opp(B)}:
   - Construct arrangement of O(k) lines
   - Overlay with vertical lines at breakpoints of opt₀,A
   - Process intervals in appropriate order (Lemma 15)
   - For each interval I:
     * Collect candidate functions on edges and faces
     * Compute lower envelope (O(Xᵢlog(Xᵢ)α(Xᵢ)) time)
     * Update result using stack
3. Return piecewise quadratic optimal function

Propagation Ordering (Lemma 15): Determine correct propagation order by proving non-crossing of corresponding path suffixes:

• If A and B have same orientation (e.g., A = opp(B)), then s < s'
• If A and B are orthogonal (e.g., A = adj(B)), then s > s'

Approximation Guarantee (Corollary 17):

• Using regular k-gon norm Gψ(Rₖ) computes CDTW exactly
• Obtain (1+ε)-approximation for 2-norm with k ∈ O(ε^(-1/2))
• Proof: 1/cos(π/k)² ≤ 1+ε

Technical Innovations

1. Geometric Duality Method: Uses duality properties of gauge functions and convex geometry to prove valley existence and positive slope properties
2. Transcendental Number Theory Application: First application of Baker's theorem to CDTW, proving stronger results than previous "cannot be expressed using radicals"
3. Avoiding Discretization: Directly works on continuous curves by exploiting piecewise linearity of polygonal norms, without discretization
4. Stack-based Dynamic Programming: Uses propagation ordering properties (Lemma 15) with stack data structure to accelerate lower envelope computation
5. Unified Framework: Established technical foundations apply to arbitrary norms and generalize to related metrics (such as partial Fréchet similarity)

Experimental Setup

Note: This is a theoretical paper whose main contributions are algorithms and complexity analysis, without traditional experimental sections. The paper focuses on:

• Theoretical proofs
• Algorithm correctness
• Complexity analysis

Theoretical Verification

1. Transcendence Verification (Section 3):
   • Constructs concrete examples verifying Theorem 11
   • Example (a): P = ⟨(1,2)ᵀ, (1,-4)ᵀ⟩, Q = ⟨(0,0)ᵀ, (5,0)ᵀ⟩
   • Computed: cdtw = ½·ln(α₁) - 1/√2 - ½·ln(α₂) + √5 + 17√2
   • where α₁ = √2-1, α₂ = √5-2
   • Proven transcendental via Lemma 10
2. Algorithm Correctness:
   • Theorem 16 proves Propagate algorithm correctness
   • Theorem 20 proves optimal function continuity
   • Lemma 19 proves path sequence convergence

Complexity Analysis

Runtime (Proposition 18):

• Total time: O(N·k²log(k)α(k))
• N: total number of quadratic pieces in all optimal functions
• α: inverse Ackermann function

Unresolved Issues:

• 1D case proven N ∈ O(n⁵)
• 2D case polynomial bound for N not established
• Main difficulty: negative-slope lines in arrangement may cause doubling behavior (Figure 5)

Experimental Results

Theoretical Results Summary

1. Non-Computability:
   • Explicitly proves CDTW under 2-norm involves transcendental numbers
   • Eliminates possibility of pure algebraic algorithms
   • Provides theoretical support for approximation algorithms
2. Algorithm Effectiveness:
   • Exact computation possible under polygonal norms
   • Obtain (1+ε)-approximation for 2-norm with k = O(ε^(-1/2))
   • No discretization of input curves required
3. Generality:
   • Valley existence applies to all norms
   • Technical framework generalizes to other metrics
   • Theorems 8 and Lemma 15 have independent value

Case Studies

Example 1 (Figure 4, Theorem 11a):

• Simple 2-segment and 1-segment curves
• Single parameter space cell
• Optimal path has 3 segments: two on valley, one horizontal
• CDTW value contains logarithmic term, proven transcendental

Example 2 (Figure 4, Theorem 11b):

• 3-segment and 1-segment curves
• Two parameter space cells
• Optimal path candidate γₛ parameterized by s ∈ 0,10
• By analyzing C'(s) = 0 solutions, prove minimizing point s* is transcendental
• Numerical verification: s* ≈ 2.08, while unique algebraic candidate s₀* ≈ 4.31

Related Work

DTW and Fréchet Distance

• Standard DTW: O(n²) time Vintsyuk 1968
• Fréchet Distance: O(n²log n) time Alt & Godau 1995
• Improved Bounds: Better upper bounds exist Gold & Sharir 2018; Buchin et al. 2017; Cheng & Huang 2025

Continuous DTW Variants

• Serra & Berthod 1994: First continuous version, continuous matching with finite summation
• Munich & Perona 1999: Equivalent definition and analysis
• Serra & Berthod 1995: Translation-invariant version based on distance vector changes
• Efrat et al. 2007: More general integral version
• Buchin 2007: Definition adopted in this paper

Exact and Approximate Algorithms

• Klaren 2020, Buchin et al. 2022: 1D polynomial-time exact algorithms
• Maheshwari et al. 2018: 2D Euclidean 2-norm pseudo-polynomial time (1+ε)-approximation
• Brankovic 2022: 2D 1-norm algorithm

Non-Computability Results

• De Carufel et al. 2014: Partial Fréchet similarity cannot be computed using radicals
• Bajaj 1988, De Carufel et al. 2014: Algebraic degree of related geometric optimization problems
• This Paper: Stronger transcendence results

Related Metrics

• Lexicographic Fréchet Distance Rote 2014
• Partial Fréchet Similarity Buchin et al. 2009
• These metrics share local optimality properties with CDTW

Conclusions and Discussion

Main Conclusions

1. Theoretical Contributions:
   • Under 2-norm, exact CDTW computation requires transcendental numbers, beyond algebraic computation models
   • Positive-slope valleys exist under arbitrary norms, ensuring algorithmic feasibility
   • Established technical foundations applicable to arbitrary norms
2. Algorithmic Contributions:
   • Provides exact algorithm under polygonal norms
   • Obtains (1+ε)-approximation for 2-norm via regular k-gons with k = O(ε^(-1/2))
   • Avoids input curve discretization
3. Open Problems:
   • Polynomial-time bounds for 2D case not yet established
   • Main challenge is potential doubling behavior from negative-slope lines in arrangements

Limitations

1. Incomplete Complexity Analysis:
   • While O(N·k²log(k)α(k)) bound provided, polynomial bound for N not established
   • 1D O(n⁵) analysis techniques do not directly generalize to 2D
2. Practical Efficiency Unverified:
   • Paper is purely theoretical without implementation and experimental evaluation
   • Actual runtime likely significantly affected by k and N
3. Approximation Factor Dependency:
   • k = O(ε^(-1/2)) means small ε requires large k
   • For example, ε = 0.01 requires k ≈ 314
4. Numerical Stability:
   • While avoiding exact transcendental computation, cumulative error issues remain (mentioned in Section 3)

Future Directions

1. Complexity Analysis:
   • Resolve polynomial bound for N in 2D case
   • Particularly address doubling behavior in Figure 5
2. Practical Implementation:
   • Implement algorithm and conduct experimental evaluation
   • Compare with existing discretization methods
3. Generalization and Application:
   • Extend techniques to related metrics like partial Fréchet similarity
   • Explore applications in other domains
4. Improved Approximation:
   • Investigate whether same approximation guarantees achievable with smaller k
   • Explore alternative approximation strategies

In-Depth Evaluation

Strengths

1. Theoretical Depth:
   • Transcendence result is important theoretical contribution to the field, stronger than previous "cannot be expressed using radicals"
   • Novel and rigorous proof technique using Baker's theorem
   • Elegant and general geometric proof of valley existence
2. Technical Rigor:
   • All theorems have complete proofs (main text or appendix)
   • Detailed mathematical derivations, particularly in Appendix B's transcendence proof
   • Considers multiple boundary cases
3. Generality:
   • Established framework applicable to arbitrary norms
   • Generalizes to related metrics (lexicographic Fréchet distance, partial Fréchet similarity)
   • Theorems 8 and Lemma 15 have independent value
4. Algorithm Design:
   • Avoiding discretization is important methodological contribution
   • Stack-based propagation exploits problem's geometric structure
   • Propagate algorithm clearly designed and easy to understand
5. Writing Quality:
   • Clear structure, progressing from motivation to theory to algorithms
   • Figures (Figures 1-9) aid understanding
   • Comprehensive related work survey

Weaknesses

1. Missing Experiments:
   • As an algorithms paper, lacks actual implementation and experimental evaluation
   • Cannot assess algorithm's practical efficiency and usability
   • Missing performance comparisons with existing methods
2. Incomplete Complexity Resolution:
   • Polynomial bound for N is critical open problem
   • No clear direction for addressing doubling behavior
   • Limits theoretical completeness of algorithm
3. Approximation Parameters:
   • k = O(ε^(-1/2)) dependency relatively weak
   • Small ε requires large k, potentially affecting practical efficiency
   • No discussion of practical k values' performance impact
4. Numerical Issues:
   • While avoiding transcendental computation, cumulative error issues mentioned in Section 3 insufficiently discussed
   • Numerical stability of piecewise quadratic functions not analyzed
5. Application Discussion:
   • Limited discussion of practical application scenarios
   • No guidance on when to use CDTW versus DTW or Fréchet distance

Impact

1. Theoretical Impact:
   • Transcendence result important progress in computational complexity of curve similarity metrics
   • Provides solid theoretical foundation for approximation algorithm necessity
   • Technical framework may inspire research on related problems
2. Practical Value:
   • (1+ε)-approximation algorithm valuable for practical applications
   • Avoiding discretization may improve solution quality
   • Actual efficiency requires experimental verification
3. Reproducibility:
   • Algorithm description detailed, theoretically reproducible
   • Lacks implementation details and code
   • Detailed proofs in Appendix aid understanding
4. Follow-up Research:
   • Open complexity problems provide clear directions for future research
   • Technical foundations generalizable to other metrics and applications
   • May inspire new algorithmic design approaches

Applicable Scenarios

1. Theoretical Research:
   • Computational complexity of curve similarity metrics
   • Algorithm design for geometric optimization problems
   • Applications of transcendental numbers in computational geometry
2. Practical Applications (Potential):
   • Trajectory similarity analysis (when sampling rate differences are large)
   • Signature verification (requiring outlier robustness)
   • Map matching (GPS trajectory matching)
   • Time series clustering
3. Inapplicable Scenarios:
   • Applications requiring real-time computation (high complexity)
   • High-dimensional data (currently limited to 2D)
   • Applications with low accuracy requirements (DTW may suffice)

References

Key Citations

1. Alt & Godau 1995: Classical Fréchet distance algorithm
2. Vintsyuk 1968: Original DTW definition
3. Baker 1990: Transcendental number theory foundations (Lemma 10 source)
4. Buchin 2007: CDTW definition source
5. Buchin, Nusser & Wong 2022: 1D CDTW exact algorithm
6. Maheshwari, Sack & Scheffer 2018: 2D CDTW approximation algorithm
7. Brankovic 2022: 2D 1-norm algorithm

Theoretical Foundations

8. Boyd & Vandenberghe 2009: Convex optimization (gauge functions)
9. Schaefer & Wolff 1999: Topological vector spaces (norm theory)
10. De Carufel et al. 2014: Partial Fréchet similarity non-computability

Overall Assessment: This is a high-quality theoretical computational geometry paper making important contributions to CDTW computational complexity and algorithm design. The transcendence result represents breakthrough progress in the field, and the technical framework demonstrates good generality. Main weaknesses are missing experimental evaluation and incomplete complexity analysis. The paper is suitable for publication at top computational geometry conferences (such as WALCOM, SoCG) and has important reference value for both theoretical researchers and those interested in curve similarity metrics.