Source-linked AI summary
Approximating CDTW Distance of Piecewise Algebraic Curves
Alperen A. Ergür, Shamik Khowala
TL;DR
Exact CDTW computation faces algebraic hardness. The paper develops structural and approximation machinery for piecewise algebraic curves and presents, to the authors’ knowledge, the first algorithm for approximating CDTW on piecewise smooth curves.
Problem
Exact CDTW computation for algebraic curves is algebraically hard, motivating approximation methods.
Source: §9 · p. 24Method
The framework characterizes optimal alignments and combines curve approximation with cost propagation using Chebyshev interpolation and Davenport–Schinzel lower envelopes.
Source: §9 · p. 24Results
To the authors’ knowledge, this is the first algorithm for approximating CDTW distance of piecewise smooth curves.
Source: §9 · p. 24Takeaways & Limitations
The work is a first step toward extending CDTW algorithms beyond piecewise linear curves.
Source: §9 · p. 24The final runtime estimate likely omits a d^2 term because the degree dependence from prior work was not rigorously extracted.
Source: §8 · p. 24
Abstract
from arXiv · showhide
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\'echet 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\'echet 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.
1 Introduction
The introduction motivates CDTW as a curve-similarity measure combining continuous alignment with accumulated cost, addressing sampling-rate and outlier sensitivities. It presents an approximation framework for piecewise algebraic curves built on structural results and algorithmic machinery.
1 Introduction
- Curve similarity supports clustering, classification, and trend spotting in time-series and trajectory data, while the appropriate measure varies by application.The introduction gives signature verification, animal tracking, and electrocardiography as example fields.Source: §1 · p. 1
1.1 Dynamic Time Warping
- The natural DTW dynamic program takes O(mn) time; later work introduced linear-time approximation and exact subquadratic algorithms [SC07].DTW was also used for speech recognition and time normalization.Source: §1.1 · p. 2
1.2 The Fr´echet Distance
- Fréchet distance considers entire curves continuously, but exact polygonal-curve computation has no strongly subquadratic algorithm unless SETH fails.Past work also extends Fréchet algorithms to piecewise smooth and algebraic curves.Source: §1.2 · p. 2
1.3 Continuous Dynamic Time Warping
- CDTW combines continuous alignment with integral cost, addressing DTW’s sampling-rate sensitivity and Fréchet distance’s outlier sensitivity, while computation for algebraic curves remains difficult.The introduction describes CDTW as a robust similarity measure for applications involving temporal distortions and outliers.Source: §1.3 · pp. 2–3
1.4 Our Contribution
- Optimal alignments are characterized, CDTW is lower-bounded using Fréchet distance, and curvature-based preprocessing creates piecewise-quadratic approximations with controlled error.The alignment characterization uses Pontryagin’s maximum principle.Source: §1.4 · p. 3
- The dynamic program computes CDTW between piecewise quadratics to target multiplicative accuracy ε; its approximation and bit-size control extend beyond function propagation used in.The approximation machinery uses Chebyshev interpolants and resultants to handle non-linear curves.Source: §1.4 · p. 3
- The contributions combine structural results and a quadratic-curve dynamic program into an FPTAS for CDTW on piecewise algebraic curves.The dynamic program targets multiplicative accuracy ε; the paper identifies this as the first FPTAS for the problem.Source: §1.4 · p. 3
2 Preliminaries
The preliminaries formulate CDTW as a path-cost problem in a parameter-space grid and establish structural tools for reasoning about optimal paths and boundary costs.
2.1 Setup and Definitions
- The input curves are represented by polynomial pieces of degree at most d, and their comparisons occupy cells in a parameter-space grid.The grid spans [0, p] × [0, q], with each cell corresponding to a pair of curve pieces.Source: §2.1 · p. 4
2.2 Structure of the Valley
- The valley is the zero set of the height function; within a cell it is either the diagonal or at most d discrete points.The discrete points satisfy u(x) − v(x) = 0.Source: §2.2 · pp. 6–7
2.3 Optimal Path Disjointness
- Optimal paths with different starting points or different end points do not intersect within a cell.The proof uses the fact that at an intersection, only one of the two paths to that point can be optimal.Source: §2.3 · p. 7
2.4 Subdivision of Boundaries with Elimination Theory
- For polynomial cost functions, boundary minimizers can be subdivided by finding critical parameter values through successive resultants.The resulting polynomial Q(t) has degree at most (d − 1)^3; between critical points, the minimizer is unique.Source: §2.4 · pp. 7–8
3 The Shape of an Optimal Path
The section characterizes optimal paths using Pontryagin’s Maximum Principle. Within a cell, paths consist of line segments and valley portions, with three possible patterns when the valley is encountered.
3 The Shape of an Optimal Path
- When neither constraint is active, the optimal curve is a line.The section derives its path characterization using Pontryagin’s Maximum Principle.Source: §3 · pp. 8–9
- An optimal path consists of line segments or portions of the valley, and both parameter coordinates are non-decreasing.For odd-p ℓp norms, the proof’s conclusion places joins at intersections with P(x) = Q(y) or x = y.Source: §3 · p. 9
- A path may reach the diagonal valley, travel along it, then leave at an optimal point with a changed slope.This is one of the three path shapes listed for a cell.Source: §3 · pp. 9–10
- If the valley consists of discrete points, a path can enter at one point and leave at another with a different direction.The section also lists paths that never touch the valley and paths that travel along a diagonal valley.Source: §3 · p. 10
4 Comparing CDTW and Fr´echet Distance for Algebraic Curves
The section compares CDTW and Fréchet distance for piecewise algebraic curves, deriving bounds using properties of optimal paths and polynomial height functions.
4 Comparing CDTW and Fréchet Distance for Algebraic Curves
- The section derives a lower bound for CDTW distance in terms of Fréchet distance, using that the optimal path is piecewise linear with joins on boundaries or the valley.The paper uses fast Fréchet-distance algorithms to obtain upper and lower bounds for CDTW(P, Q).Source: §4 · pp. 10–11
- CDTW(P, Q) ≤ Frechet(P, Q)√(p + q), using a path that realizes the Fréchet distance.The path length is bounded by p + q, and the height function along it is bounded by Frechet(P, Q)^2.Source: §4 · p. 10
- When the curves do not intersect, there is no valley, so the analysis uses the case in which the path never touches the valley.The section also considers path cases in which the last or first valley touch falls outside the interval around the maximum height.Source: §4 · p. 11
5 Piecewise Quadratic Approximation via Turning Angles
The section constructs piecewise quadratic approximations guided by total turning angle and bounds their effect on CDTW distance. The resulting guarantee extends to piecewise algebraic curves.
5 Piecewise Quadratic Approximation via Turning Angles
- Total turning angle supplies a local approximation measure, motivating piecewise quadratic Bezier approximations of higher-degree curves.The section draws on the connection between integral curvature and total turning angle.Source: §5 · p. 12
- On intervals where curvature does not change sign, the approximation uses a quadratic Bezier curve whose control point is the intersection of endpoint tangents.The curves are subdivided at critical points before constructing these approximations.Source: §5 · p. 12
- The deviation between the curve and its quadratic approximation is bounded using the chord length and total turning angle of each piece.The curves and approximations lie within the tangent triangle, whose altitude bounds their distance.Source: §5 · p. 12
- |˜dCDTW(P, Q) − dCDTW(P, Q)| ≤ ε0 for the constructed piecewise quadratic approximations.The guarantee applies to piecewise algebraic curves without change.Source: §5 · p. 14
6 Boundary Cost Functions and Cost Propagation
This section propagates boundary cost functions through cells, producing candidate costs on each output boundary. Its framework analyzes arbitrary-degree curves, while the paper's algorithm applies it to piecewise quadratics.
6 Boundary Cost Functions and Cost Propagation
- The propagation theorem handles arbitrary-degree curves, but the paper's algorithm first approximates its inputs by piecewise quadratics.The authors cannot perform exact propagation in their nonlinear setting and instead control approximation error on output-boundary subintervals.Source: §6 · p. 14
- Each input cost subsegment propagates to O(1) continuous candidate branches, with critical transition points computed by exact algebraic real root isolation in O(1) time.The theorem states this for curves of arbitrary degree and bounded-degree input cost functions.Source: §6 · p. 14
- For straight-line paths, the output cost minimizes the sum of the input boundary cost and the integrated height along the path.The minimizing entry parameter satisfies a polynomial equation; roots introduced by squaring are checked and removed.Source: §6 · p. 15
- When the valley is the diagonal, propagation forms a cumulative minimum of entry costs; for discrete valley points, it updates minima from left to right.The passage describes O(1) time for the diagonal case and O(k)=O(d)=O(1) for the discrete-point case.Source: §6 · p. 17
7 Computing CDTW Distance of Piecewise Quadratic Curves
This section develops an approximation engine for CDTW on piecewise quadratic curves, propagating boundary cost functions across diagonals. It bounds lower-envelope size and construction time and describes quintic interpolation to control approximation error and coefficient bit-size.
7.1 Error and Coefficient Bit-Size Bounds
- Degree-10 algebraic branches generally lack closed forms, and feeding them directly into the next propagation step would compound degree and bit-size.The algorithm instead resets each branch to a degree-5 polynomial before reuse.Source: §7.1 · pp. 17–18
- Resetting each algebraic output branch to a quintic interpolant keeps propagation inputs degree-bounded and limits accumulated error along any path to ε0.Theorem 7.1 also states that the resulting coefficient bit-size bound is independent of the diagonal index.Source: §7.1 · p. 18
7.1.1 Error Bounds for The Quintic Approximation
- Near branch singularities, the method replaces each branch on a small buffer by a constant, then interpolates the remaining real-analytic intervals using further subdivisions.The buffer approximation incurs O(σ) error and adds O(1) pieces per singularity.Source: §7.1.1 · p. 19
7.1.2 Coefficient Bit-Size Bound for the Quintic
- The quintic interpolant has bounded coefficient bit-size, and its output size does not grow as propagation advances across diagonals.The bound is retained inductively with a constant independent of M, N, ε0, and the diagonal index.Source: §7.1.2 · p. 21, §7.1.3 · p. 21
7.2 Bounding the Complexity
- The number of boundary subsegments satisfies |A_k| ≤ 3k^2, because noncrossing optimal paths make the mapping to source intervals monotonic and limit each pair’s switches.The algorithm’s overall complexity is O(T + Tenv), where T counts boundary cost-function pieces and Tenv is the time for global lower envelopes.Source: §7.2 · pp. 21–22
- The lower envelope along Ak has at most λ_{κ+2}(mk) pieces, which is O(mk) for fixed κ=O(1).The Davenport–Schinzel bound applies because candidate branches intersect pairwise only O(1) times.Source: §7.2 · p. 22
- Spatially ordered candidate curves permit a linear-time, single-pass stack sweep to build each diagonal’s lower envelope.The passage attributes their spatial ordering to the non-crossing path property.Source: §7.2 · p. 23
- Quintic interpolation covers T=O((M+N)^3) boundary polynomial pieces, and ApproxCDTW computes CDTW(P, Q) within additive error ε0.The supplied passages do not include the resulting overall bit-complexity expression.Source: §7.2 · p. 23
8 An FPTAS for CDTW Distance of Piecewise Algebraic Curves
The algorithm converts a multiplicative CDTW target into an additive error budget, then approximates algebraic curves and computes CDTW on the resulting piecewise quadratic curves. Its degree-dependence analysis treats the degree as constant and may omit a d^2 term.
8 An FPTAS for CDTW Distance of Piecewise Algebraic Curves
- The input consists of two piecewise algebraic curves with m and n pieces, arc lengths p and q, and polynomial pieces of degree d and bit-size at most τ.The construction first computes their Fréchet distance and derives a lower bound δ on CDTW, independent of ε, to bridge additive and multiplicative error.Source: §8 · p. 23
- The target multiplicative error ε sets the additive error bound to ε0 = δε.The algorithm divides both curves using turning angles, creates quadratic Bézier approximations, then approximates the CDTW distance of those curves.Source: §8 · p. 24
- The analysis treats the polynomial degree d as constant, so the final estimate may be missing a d^2 factor.The authors did not rigorously extract the degree dependence from the cited Fréchet algorithms and believe it is likely sub-quadratic.Source: §8 · p. 24
9 Conclusion
The paper presents an approximation framework for CDTW distance between piecewise algebraic curves, motivated by the algebraic hardness of exact computation. It combines structural results and approximation machinery, and the authors describe it as a first step beyond piecewise linear curves.
9 Conclusion
- The framework approximates CDTW distance under the squared Euclidean ℓ2 norm to any user-specified error ε.The authors state that exact computation is algebraically hard.Source: §9 · p. 24
- Pontryagin’s maximum principle yields optimal alignments made of straight segments or segments along valleys of the height function.A new comparison with Fréchet distance for piecewise smooth curves supports a fast, coarse CDTW approximation.Source: §9 · p. 24
- The algorithm approximates algebraic curves with piecewise quadratic curves and propagates optimal costs using quintic Chebyshev interpolation and Davenport–Schinzel lower envelopes.The authors report strict bounds on computational complexity and accumulated errors.Source: §9 · p. 24
- To the authors’ knowledge, this is the first algorithm for approximating CDTW distance of piecewise smooth curves.They identify extending CDTW algorithms beyond piecewise linear curves as a first step and call for faster algorithms for broader curve families.Source: §9 · p. 24
A Pseudo-Code of the Main Algorithms
The pseudocode computes an additive approximation by propagating cost functions across diagonal wavefronts of curve-pair cells. It combines cell-level propagation, approximation of propagated functions, and lower-envelope reduction.
A Pseudo-Code of the Main Algorithms
- The main procedure initializes boundary costs, sweeps diagonal wavefronts, propagates active curve pieces through cells, and returns an ε0-additive approximation of CDTW cost.At each wavefront it reduces the candidate curves with a global lower envelope.Source: A Pseudo-Code of the Main Algorithms · p. 27
- Cell propagation handles three types: straight propagation, propagation through a diagonal valley with a cumulative minimum, and propagation over discrete valley points.The resulting functions are quintic-approximated before being returned.Source: A Pseudo-Code of the Main Algorithms · p. 28
- QuinticApproximate isolates roots to partition the input interval into regimes, then uses six Chebyshev nodes and a Lagrange interpolant in Regime 1.For Regime 2, it replaces a buffer around the singularity with a constant and recurses on the remaining interval.Source: A Pseudo-Code of the Main Algorithms · p. 29
- StraightPropagation evaluates candidate functions at interval endpoints and valid real algebraic root branches of the stationarity equation.CumulativeMin replaces intervals after qualifying local minima with horizontal constant segments; GlobalLowerEnvelope maintains the lower envelope with an active stack.Source: A Pseudo-Code of the Main Algorithms · pp. 29–30