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

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

doi:10.4230/LIPIcs.ICALP.2026.47

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

Kevin Buchin

Technical University Dortmund, Germany Maike Buchin

Ruhr University Bochum, Germany Jan Erik Swiadek

Ruhr University Bochum, Germany Sampson Wong

University of Copenhagen, Denmark

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.

Keywords and phrases:

Continuous Dynamic Time Warping, Curve Similarity, Geometric Approximation Algorithm

Category:

Track A: Algorithms, Complexity and Games

Funding:

Sampson Wong: Supported by the European Union’s Marie Skłodowska-Curie Actions Postdoctoral Fellowship, grant no. 101146276.

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Computational geometry ; Theory of computation

\rightarrow

Approximation algorithms analysis

Editors:

Sayan Bhattacharya, Danupon Nanongkai, Michael Benedikt, and Gabriele Puppis

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

There exist several desirable properties for curve similarity measures [22, 23], two of which are tolerance to outliers and robustness to different sampling rates. As the Fréchet distance fails to provide the former, whereas Dynamic Time Warping struggles with the latter, these popular measures have drawbacks for applications. Continuous Dynamic Time Warping (CDTW) is an alternative that combines both abovementioned properties by minimising a path integral of distances between continuously and monotonically matched points on two polygonal curves. Our considered CDTW formulation [16, 15, 3, 7, 2, 5] originates from a summed version of the Fréchet distance introduced in [8]. There exist other related definitions [20, 21, 17, 1, 11, 14], and we refer to [7, Section 1] as well as [5, Section 1.1] for brief overviews of these.

On the practical side, the robustness of CDTW and its ability to yield high-quality solutions across different application domains have been observed in experiments [1, 11, 3]. Also, reasonable running times on realistic data have been reported [3, 2]. On the theoretical side, however, CDTW still lacks algorithms that guarantee both a good approximation factor and an efficient running time in 2D and beyond. Many existing approaches are approximations or heuristics that proceed via discretising the input curves [1, 11, 16, 15, 3, 14]. These include a generic additive approximation algorithm [15, 3], and a pseudo-polynomial-time $(1+\varepsilon)$ -approximation for 2D CDTW under the Euclidean $2$ -norm [16]. The latter has running time $O(\zeta^{4}n^{4}/\varepsilon^{2}\cdot\log(\zeta n/\varepsilon))$ , where $n$ is the complexity and $\zeta$ is the spread of the given polygonal curves. That means the running time depends on the maximum ratio $\zeta$ of a pair of curve segment lengths. Such dependencies are typical for discretisation approaches.

A different type of approach, which enables exact computations, propagates functions arising from integration within a dynamic program [6, 15, 7, 2, 5]. This results in a polynomial running time of $O(n^{5})$ for CDTW in 1D [7]. However, in 2D the algorithmic complexity of computing CDTW is as yet unknown. On the one hand, it has been shown that 2D CDTW cannot even be computed exactly under the $2$ -norm when restricted to algebraic operations [5]. On the other hand, function propagation approaches have only been made to work with polygonal norms like the $1$ -norm [2, 5]. These give piecewise linear integrands and piecewise quadratic cost functions similar to 1D. By converging to the unit disk, polygonal norms provide a $(1+\varepsilon)$ -approximation for CDTW under the $2$ -norm without a dependency on the curves’ spread. However, the 2D dynamic program may involve more complicated propagation patterns [5, Section 4.2]. Those have so far prevented any 2D generalisation of the quite technical polynomial-time result that was achieved in 1D.

Our Contributions

We show that we can circumvent the 2D propagation patterns that potentially have an exponential complexity, in exchange for an approximation factor $\beta\leq 5$ . This relies on a new bound for certain CDTW integrals, which we establish in Section 3.1. It is open whether the bound is tight, and any improvement to $\beta$ would transfer to the following results. Applying this building block, we develop a CDTW algorithm that is outlined in Section 3.2 and then analysed in Section 4. After proving its approximation factor, we bound its time complexity by combining ideas from [7] with novel insights. For CDTW in $(\mathbb{R}^{2},\mbox{$\|\cdot\|_{1}$})$ we achieve a $5$ -approximation with running time $O(n^{5})$ . This is the first polynomial-time constant-factor result for 2D CDTW. We subsequently extend our algorithm from the $1$ -norm $\|\cdot\|_{1}$ to the class of polygonal norms. This is based on the framework of [5], which we generalise to facilitate approximations for not only the $2$ -norm $\|\cdot\|_{2}$ but also any other norm on $\mathbb{R}^{2}$ . To that end, we exploit that any fixed norm $\|\cdot\|$ on $\mathbb{R}^{d}$ is $(1+\varepsilon)$ -approximated by a polyhedral norm of complexity $O(\varepsilon^{(1-d)/2})$ . Here, fixed means that we treat the description complexity of $\|\cdot\|$ , including the dimension $d$ , as a constant. Putting things together, we obtain an approximation algorithm with factor $5+\varepsilon$ and running time $O(n^{5}/\varepsilon^{1/2})$ for 2D CDTW under any fixed norm and for any $\varepsilon>0$ . In the imbalanced case, where one of the given polygonal curves has some smaller complexity $m\in o(n)$ , the term $n^{5}$ in our time bounds may be replaced by $n^{4}m$ . Note that the guaranteed bounds might be pessimistic. In particular, even if $\beta=5$ is a tight bound for the approximated CDTW integrals, it is unclear whether there are any curves for which our algorithm approximates within factor close to $\beta$ .

On a technical level, we expand the toolbox for CDTW algorithms by demonstrating that an integration-based building block and a tailored function propagation scheme can enable CDTW approximations without discretisations of any form. Combining our techniques with the approach of approximating the Euclidean $2$ -norm via polygonal norms yields polynomial-time computations for 2D CDTW under $\|\cdot\|_{2}$ without any significant loss of accuracy for the first time. Even though polygonal norms have already been used in [5], no attempt at a fine-grained running time analysis was made there, after highlighting the obstacle that we deal with approximatively here. Furthermore, our running time analysis is more streamlined and insightful than that from [7]. We avoid a large case distinction by identifying core principles behind the complexity of function propagations, which generalise beyond some properties unique to 1D. In addition to advancing the understanding of propagation patterns, this enables an improvement upon previous algorithms: We compute lower envelopes of quadratic pieces in a single pass instead of multiple passes.

2 Preliminaries

A polygonal curve $P$ in a normed real vector space $(\mathbb{R}^{d},\mbox{$\|\cdot\|$})$ consists of $n\in\mathbb{N}$ consecutive line segments induced by a sequence $\langle p_{0},\dotsc,p_{n}\rangle$ of vertices, where $p_{i}\neq p_{i-1}$ for all $i\in\{1,\dotsc,n\}$ . We write $P_{\leq i}:=\langle p_{0},\dotsc,p_{i}\rangle$ , where $i\in\{0,\dotsc,n\}$ , for the prefix subcurves of $P$ . The following definitions are based on [5], which provides a robust CDTW formulation under any norm.

Definition 1 ([5, Definition 1]).

Let $P, Q$ be two polygonal curves in $(\mathbb{R}^{d},\mbox{$\|\cdot\|$})$ . The measure Continuous Dynamic Time Warping (CDTW) of $P, Q$ under $\|\cdot\|$ is defined by

\mathrm{cdtw}_{\|\cdot\|}(P,Q):=\inf_{(f,g)\in\Pi_{[0,1]}(P)\times\Pi_{[0,1]}(% Q)}\int_{0}^{1}\|f(t)-g(t)\|\cdot\left\|\begin{pmatrix}\|f^{\prime}(t)\|\\ \|g^{\prime}(t)\|\end{pmatrix}\right\|_{1}\>\mathrm{d}t\text{,}

where the sets $\Pi_{[a,b]}(P)$ and $\Pi_{[a,b]}(Q)$ contain all piecewise continuously differentiable functions defined on the interval $[a,b]$ that monotonically parametrise $P$ or $Q$ respectively.

The arc length of $P$ under $\|\cdot\|$ is $\|P\|:=\sum_{i=1}^{n}\|p_{i}-p_{i-1}\|$ . As the arc length is invariant to reparametrisation, we have $\int_{a}^{b}\|f^{\prime}(t)\|\>\mathrm{d}t=\|P\|$ for all $f\in\Pi_{[a,b]}(P)$ . We denote the arc length parametrisation of $P$ with constant speed $1$ under $\|\cdot\|$ by $P_{\|\cdot\|}\colon[0,\|P\|]\to\mathbb{R}^{d}$ .

Definition 2 ([5, Definitions 2 and 12]).

The parameter space of two polygonal curves $P, Q$ under $\|\cdot\|$ is $[0,\|P\|]\times[0,\|Q\|]$ . Each segment pair of $P=\langle p_{0},\dotsc,p_{n}\rangle$ and $Q=\langle q_{0},\dotsc,q_{m}\rangle$ is associated with a cell $C_{i,j}:=[\|P_{\leq i-1}\|,\|P_{\leq i}\|]\times[\|Q_{\leq j-1}\|,\|Q_{\leq j}\|]$ in their parameter space, where $(i,j)\in\{1,\dotsc,n\}\times\{1,\dotsc,m\}$ . The north/east/south/west border of $C_{i,j}$ parametrises along that side of $C_{i,j}$ , e.g. its north border is $[\|P_{\leq i-1}\|,\|P_{\leq i}\|]\to\mathbb{R}^{2},t\mapsto(t,\|Q_{\leq j}\|)^% {\mathsf{T}}$ .

The monotone matchings of $P$ and $Q$ correspond to monotone paths in parameter space. Let $\sigma:=\|P\|+\|Q\|$ , and let $\Gamma_{\|\cdot\|}(P,Q)$ be the set of functions $\gamma\colon[0,\sigma]\to[0,\|P\|]\times[0,\|Q\|]$ such that there are parametrisations $(f,g)\in\Pi_{[0,\sigma]}(P)\times\Pi_{[0,\sigma]}(Q)$ with $\gamma_{1}(s)=\int_{0}^{s}\|f^{\prime}(t)\|\>\mathrm{d}t$ and $\gamma_{2}(s)=\int_{0}^{s}\|g^{\prime}(t)\|\>\mathrm{d}t$ as well as $\|\gamma^{\prime}(s)\|_{1}=\|f^{\prime}(s)\|+\|g^{\prime}(s)\|=1$ for all $s\in[0,\sigma]$ .

Definition 3 ([5, Definition 3]).

Let $x,y\in[0,\|P\|]\times[0,\|Q\|]$ be two points with $x\preceq y$ , i.e. $x_{1}\leq y_{1}$ and $x_{2}\leq y_{2}$ , for polygonal curves $P, Q$ . An $(x,y)$ -path is a restriction $\widehat{\gamma}:=\allowbreak\gamma|_{[\|x\|_{1},\|y\|_{1}]}$ of any function $\gamma\in\smash{\Gamma_{\|\cdot\|}}(P,Q)$ with $\gamma(\|x\|_{1})=x$ and $\gamma(\|y\|_{1})=y$ . It is called optimal for $P, Q$ under $\|\cdot\|$ if it minimises $\mathrm{cost}_{\|\cdot\|}(\widehat{\gamma}):=\int_{\|x\|_{1}}^{\|y\|_{1}}\|P_{% \|\cdot\|}(\widehat{\gamma}_{1}(t))-Q_{\|\cdot\|}(\widehat{\gamma}_{2}(t))\|\>% \mathrm{d}t$ among all $(x,y)$ -paths. We write $\mathrm{opt}_{\|\cdot\|}(x,y)$ for the cost of such an optimal $(x,y)$ -path.

It is $\mathrm{cdtw}_{\|\cdot\|}(P,Q)=\mathrm{opt}_{\|\cdot\|}(\mathbf{0},(\|P\|,\|Q% \|)^{\mathsf{T}})$ by construction, where $\mathbf{0}$ denotes the origin. Given a cell border $\mathcal{B}\colon\mathrm{dom}(\mathcal{B})\to\mathbb{R}^{2}$ , we define its optimum function $\mathrm{opt}_{0,\mathcal{B}}\colon\mathrm{dom}(\mathcal{B})\to\mathbb{R}_{\geq 0}$ by $\mathrm{opt}_{0,\mathcal{B}}(t):=\mathrm{opt}_{\|\cdot\|}(\mathbf{0},\mathcal{% B}(t))$ for $t\in\mathrm{dom}(\mathcal{B})$ . In a cell under $\|\cdot\|$ we further define for each pair of south/west input border $\mathcal{A}$ and north/east output border $\mathcal{B}$ a function $\mathrm{opt}_{\mathcal{A},\mathcal{B}}$ by

\mathrm{opt}_{\mathcal{A},\mathcal{B}}(s,t):=\mathrm{opt}_{\|\cdot\|}(\mathcal% {A}(s),\mathcal{B}(t))\quad\text{for }(s,t)\in\mathrm{dom}(\mathcal{A})\times% \mathrm{dom}(\mathcal{B})\text{ with }\mathcal{A}(s)\preceq\mathcal{B}(t)\text% {.}

The optimal paths realising $\mathrm{opt}_{\mathcal{A},\mathcal{B}}$ are characterised by Theorem 4, and possible resulting shapes of these optimal paths within different cells are illustrated in Figure 1.

Theorem 4 ([5, Section 2]).

Let $P, Q$ be two polygonal curves in $(\mathbb{R}^{2},\mbox{$\|\cdot\|$})$ , and let $C$ be a parameter space cell. There exists a line $\ell\subseteq\mathbb{R}^{2}$ of positive slope such that for any choice of two points $x,y\in C$ with $x\preceq y$ the following $(x,y)$ -path $\gamma$ is optimal for $P, Q$ under $\|\cdot\|$ .

(a)

If $\ell$ intersects the bounding box $\Xi:=[x_{1},y_{1}]\times[x_{2},y_{2}]$ , then $\gamma$ traces line segments from $x$ to $\xi_{x}$ to $\xi_{y}$ to $y$ , where $\xi_{x},\xi_{y}\in\ell\cap\Xi$ share a coordinate with $x, y$ respectively.
(b)

If $\ell$ does not intersect the bounding box $\Xi$ , then $\gamma$ traces line segments from $x$ to $\xi$ to $y$ , where the single bending point $\xi\in\{(x_{1},y_{2})^{\mathsf{T}},(y_{1},x_{2})^{\mathsf{T}}\}$ is the point closest to $\ell$ in $\Xi$ .

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 $\|\cdot\|$ measures both distances between curve points and speeds of curve parametrisations [5], while the $1$ -norm $\|\cdot\|_{1}$ combines these speeds within the CDTW path integral [8, 16, 7, 2, 5]. Also, Theorem 4 only holds in 1D and 2D. See the full version for a 3D counterexample.

3 Towards a Polynomial Bound

The idea behind function propagation approaches for exact CDTW algorithms is propagating costs of optimal paths through the parameter space cells and successively computing optimum functions in a dynamic program. After $\mathrm{opt}_{0,\mathcal{A}}$ has been computed for each input border $\mathcal{A}$ of some cell $C$ , one can use Theorem 4 to determine $\mathrm{opt}_{0,\mathcal{B}}$ for each output border $\mathcal{B}$ of $C$ . If the CDTW integrands are piecewise linear, as it is the case in 1D [7] or under polygonal norms in 2D such as the $1$ -norm or $\infty$ -norm [2, 5], then all optimum functions of borders are piecewise quadratic (cf. [5, Lemma 14]). The central challenge for the running time analysis lies in bounding the total number of quadratic pieces over all optimum functions [20, 17, 7, 5].

3.1 Building Block

In general, the possible propagation patterns and their complexity in terms of how the number of quadratic pieces is growing are still not well understood. The polynomial bound for the exact 1D algorithm relies heavily on the fact that the quadratic pieces on the output borders of a cell can be assigned monotonically to parent pieces on the cell’s input borders (cf. [7, Lemma 13 and Definition 18]). However, this is insufficient on its own already in 2D under the $1$ -norm: Certain optimal paths originating from Theorem 4b may hypothetically cause an exponential growth of propagated pieces in 2D, even though there is a monotone assignment to parent pieces. In short, the obstacle for bounding the number of pieces occurs when the paths’ bending points move freely within the cell. This yet unresolved issue was highlighted in [5, Section 4.2]. To tackle the absence of means for finding general tight bounds, our approach instead aims to ensure that the complexity created by such paths during the propagation of path costs in the dynamic program remains low. We henceforth call them unhappy paths within this paper.

Definition 5.

Let $\gamma$ be an optimal $(x,y)$ -path as in Theorem 4. If each bending point of $\gamma$ lies on $\ell$ or on the boundary of the cell $C$ , then $\gamma$ is happy w.r.t. $\ell$ . Else, $\gamma$ is unhappy.

See the fourth cell of Figure 1 for an unhappy path. As our first contribution, we show that the cost of any (unhappy) optimal $(x,y)$ -path $\gamma$ from Theorem 4b is approximated within factor at most $5$ by choosing the worse of the two possible options for the single bending point $\xi$ of $\gamma$ . This changes whether a path first travels vertically and then horizontally or vice versa, as shown in Figure 2. Note that the paths from Theorem 4a are always happy.

(a) Considered

(x,y)

-paths.

(b) Curve matching of

\gamma_{xy}

.

(c) Curve matching of

\gamma_{yx}

.

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 $\|\cdot\|$ 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)\mapsto\|p-q\|$ induced by $\|\cdot\|$ .

Lemma 6.

Let $x,y\in C$ be two points with $x\preceq y$ , where $C$ is a parameter space cell of polygonal curves $P, Q$ in $(\mathbb{R}^{d},\mbox{$\|\cdot\|$})$ . Consider the $(x,y)$ -path $\gamma_{xy}$ tracing line segments from $x$ to $(x_{1},y_{2})^{\mathsf{T}}$ to $y$ , and the $(x,y)$ -path $\gamma_{yx}$ tracing line segments from $x$ to $(y_{1},x_{2})^{\mathsf{T}}$ to $y$ . Their costs under $\|\cdot\|$ satisfy $1/5\cdot\mathrm{cost}_{\|\cdot\|}(\gamma_{xy})\leq\mathrm{cost}_{\|\cdot\|}(% \gamma_{yx})\leq 5\cdot\mathrm{cost}_{\|\cdot\|}(\gamma_{xy})$ .

Proof.

We show only the second inequality, as the first one is entirely symmetric. To make the notation of this proof more concise, we write $p_{s}:=P_{\|\cdot\|}(s)\in\mathbb{R}^{d}$ and $q_{t}:=Q_{\|\cdot\|}(t)\in\mathbb{R}^{d}$ for parameters $(s,t)\in[x_{1},y_{1}]\times[x_{2},y_{2}]$ as well as $\overline{pq}:=\|p-q\|$ for points $p,q\in\smash{\mathbb{R}^{d}}$ .

As $\gamma_{xy}$ and $\gamma_{yx}$ trace horizontal and vertical line segments, Definition 3 implies that their cost integrands on these respective segments correspond to $s\mapsto\overline{p_{s}q_{t}}$ , where $s\in[x_{1},y_{1}]$ varies and $t\in\{x_{2},y_{2}\}$ is fixed, and to $t\mapsto\overline{p_{s}q_{t}}$ , where $t\in[x_{2},y_{2}]$ varies and $s\in\{x_{1},y_{1}\}$ is fixed. We thus also use the shorthands $p_{x}:=p_{x_{1}}$ , $p_{y}:=p_{y_{1}}$ , $q_{x}:=q_{x_{2}}$ , and $q_{y}:=q_{y_{2}}$ . By applying the triangle inequality and symmetry that are induced by the norm $\|\cdot\|$ , we then obtain

	$\displaystyle\mathrm{cost}_{\\|\cdot\\|}(\gamma_{yx})-\mathrm{cost}_{\\|\cdot\\|}(% \gamma_{xy})$	$\displaystyle=\int_{x_{1}}^{y_{1}}\overline{p_{s}q_{x}}\>\mathrm{d}s+\int_{x_{% 2}}^{y_{2}}\overline{p_{y}q_{t}}\>\mathrm{d}t-\int_{x_{2}}^{y_{2}}\overline{p_% {x}q_{t}}\>\mathrm{d}t-\int_{x_{1}}^{y_{1}}\overline{p_{s}q_{y}}\>\mathrm{d}s$
		$\displaystyle=\int_{x_{1}}^{y_{1}}\overline{p_{s}q_{x}}-\overline{p_{s}q_{y}}% \>\mathrm{d}s+\int_{x_{2}}^{y_{2}}\overline{p_{y}q_{t}}-\overline{p_{x}q_{t}}% \>\mathrm{d}t$
		$\displaystyle\leq\int_{x_{1}}^{y_{1}}\overline{q_{x}q_{y}}\>\mathrm{d}s+\int_{% x_{2}}^{y_{2}}\overline{p_{x}p_{y}}\>\mathrm{d}t=2\cdot\overline{p_{x}p_{y}}% \cdot\overline{q_{x}q_{y}}\text{.}$

The final equality holds because the integrands do not depend on the variables $s$ and $t$ , while the integration intervals are of length $y_{1}-x_{1}=\overline{p_{x}p_{y}}$ and $y_{2}-x_{2}=\overline{q_{x}q_{y}}$ respectively. Note that we have $y_{1}-x_{1}=\overline{p_{x}p_{y}}$ due to $x,y\in C$ for the given cell $C$ , which means that $p_{x}$ and $p_{y}$ lie on a single curve segment of $P$ . We similarly have $y_{2}-x_{2}=\overline{q_{x}q_{y}}$ . Intuitively, the cost difference between $\gamma_{yx}$ and $\gamma_{xy}$ is at most two times the bounding box area of $x$ and $y$ . Together with $0\leq(\overline{p_{x}p_{y}}-\overline{q_{x}q_{y}})^{2}=\overline{p_{x}p_{y}}^{% 2}+\overline{q_{x}q_{y}}^{2}-2\cdot\overline{p_{x}p_{y}}\cdot\overline{q_{x}q_% {y}}$ , we therefore arrive at

\mathrm{cost}_{\|\cdot\|}(\gamma_{yx})\leq\mathrm{cost}_{\|\cdot\|}(\gamma_{xy% })+2\cdot\overline{p_{x}p_{y}}\cdot\overline{q_{x}q_{y}}\leq\mathrm{cost}_{\|% \cdot\|}(\gamma_{xy})+\overline{p_{x}p_{y}}^{2}+\overline{q_{x}q_{y}}^{2}\text% {,}

so it remains to show $\overline{p_{x}p_{y}}^{2}+\overline{q_{x}q_{y}}^{2}\leq 4\cdot\mathrm{cost}_{% \|\cdot\|}(\gamma_{xy})$ in order to get the claimed result.

We consider $\int_{x_{2}}^{y_{2}}\overline{p_{x}q_{t}}\>\mathrm{d}t$ , which is the first term of $\mathrm{cost}_{\|\cdot\|}(\gamma_{xy})$ , and pick a $\lambda\in[x_{2},y_{2}]$ such that both $\overline{q_{x}q_{\lambda}}\leq\overline{p_{x}q_{x}}$ and $\overline{q_{\lambda}q_{y}}\leq\overline{p_{x}q_{y}}$ hold. This is feasible as follows: If $\overline{q_{x}q_{y}}\leq\overline{p_{x}q_{x}}$ , then $\lambda:=y_{2}$ with $q_{\lambda}=q_{y}$ works. Else, we have $\overline{q_{x}q_{y}}\geq\overline{p_{x}q_{x}}$ and can pick $\lambda$ with $\overline{q_{x}q_{\lambda}}=\overline{p_{x}q_{x}}$ , which implies $\overline{q_{\lambda}q_{y}}=\overline{q_{x}q_{y}}-\overline{q_{x}q_{\lambda}}=% \overline{q_{x}q_{y}}-\overline{p_{x}q_{x}}\leq\overline{p_{x}q_{y}}$ via $x,y\in C$ and the triangle inequality.

We now split the interval $[x_{2},\lambda]$ into $k\in\mathbb{N}$ subintervals, each of length $\frac{1}{k}\cdot(\lambda-x_{2})=\frac{1}{k}\cdot\overline{q_{x}q_{\lambda}}$ . For every value $t$ on the $i$ -th subinterval this gives $\overline{q_{x}q_{t}}\leq\frac{i}{k}\cdot\overline{q_{x}q_{\lambda}}$ , so together we have

\overline{p_{x}q_{t}}\geq\overline{p_{x}q_{x}}-\overline{q_{x}q_{t}}\geq% \overline{q_{x}q_{\lambda}}-\frac{i}{k}\cdot\overline{q_{x}q_{\lambda}}=\frac{% k-i}{k}\cdot\overline{q_{x}q_{\lambda}}\quad\text{if }t-x_{2}\in\left[\frac{i-% 1}{k}\cdot\overline{q_{x}q_{\lambda}},\frac{i}{k}\cdot\overline{q_{x}q_{% \lambda}}\right]\text{,}

which bounds the integrand from below. Summing this over all $i\in\{1,\dotsc,k\}$ yields

\int_{x_{2}}^{\lambda}\overline{p_{x}q_{t}}\>\mathrm{d}t\geq\frac{1}{k}\cdot% \overline{q_{x}q_{\lambda}}\cdot\sum_{i=1}^{k}\frac{k-i}{k}\cdot\overline{q_{x% }q_{\lambda}}=\frac{1}{k}\cdot\overline{q_{x}q_{\lambda}}\cdot\frac{(k-1)\cdot k% }{2k}\cdot\overline{q_{x}q_{\lambda}}=\frac{k-1}{2k}\cdot\overline{q_{x}q_{% \lambda}}^{2}\text{.}

Since we also have $\overline{q_{\lambda}q_{y}}\leq\overline{p_{x}q_{y}}$ by choice of $\lambda$ , we similarly obtain $\int_{\lambda}^{y_{2}}\overline{p_{x}q_{t}}\>\mathrm{d}t\geq\frac{k-1}{2k}% \cdot\overline{q_{\lambda}q_{y}}^{2}$ . Putting these together gives a lower bound for the first term of $\mathrm{cost}_{\|\cdot\|}(\gamma_{xy})$ . That means

\int_{x_{2}}^{y_{2}}\overline{p_{x}q_{t}}\>\mathrm{d}t=\int_{x_{2}}^{\lambda}% \overline{p_{x}q_{t}}\>\mathrm{d}t+\int_{\lambda}^{y_{2}}\overline{p_{x}q_{t}}% \>\mathrm{d}t\geq\frac{k-1}{2k}\cdot(\overline{q_{x}q_{\lambda}}^{2}+\overline% {q_{\lambda}q_{y}}^{2})\geq\frac{k-1}{4k}\cdot\overline{q_{x}q_{y}}^{2}

by utilising $2\cdot(\overline{q_{x}q_{\lambda}}^{2}+\overline{q_{\lambda}q_{y}}^{2})=(% \overline{q_{x}q_{\lambda}}+\overline{q_{\lambda}q_{y}})^{2}+(\overline{q_{x}q% _{\lambda}}-\overline{q_{\lambda}q_{y}})^{2}\geq(\overline{q_{x}q_{\lambda}}+% \overline{q_{\lambda}q_{y}})^{2}=\overline{q_{x}q_{y}}^{2}$ in the final inequality. Proceeding analogously for the second term of $\mathrm{cost}_{\|\cdot\|}(\gamma_{xy})$ results in

\mathrm{cost}_{\|\cdot\|}(\gamma_{xy})=\int_{x_{2}}^{y_{2}}\overline{p_{x}q_{t% }}\>\mathrm{d}t+\int_{x_{1}}^{y_{1}}\overline{p_{s}q_{y}}\>\mathrm{d}s\geq% \frac{k-1}{4k}\cdot(\overline{q_{x}q_{y}}^{2}+\overline{p_{x}p_{y}}^{2})% \xrightarrow[]{k\to\infty}\frac{1}{4}\cdot(\overline{p_{x}p_{y}}^{2}+\overline% {q_{x}q_{y}}^{2})

and hence $\overline{p_{x}p_{y}}^{2}+\overline{q_{x}q_{y}}^{2}\leq 4\cdot\mathrm{cost}_{% \|\cdot\|}(\gamma_{xy})$ as required above, which completes the proof. $\hfill\blacktriangleleft$

$\blacktriangleright$ Remark 7.

It remains open whether the factor of $5$ is tight in general. The greatest lower bound that we know of occurs already in 1D: Consider $p_{x}:=0$ , $p_{y}:=\phi+1$ , $q_{x}:=\phi$ , and $q_{y}:=2\phi+1$ , where $\phi:=(1+\sqrt{5})/2$ is the golden ratio. This yields a factor of $2\phi+1\approx 4.236$ . By analysing the trade-off between the inequalities in the above proof, one can likely improve the upper bound in 1D from $5$ to $2\phi+1$ , but closing the gap for $d\geq 2$ seems difficult.

Lemma 6 for the first time allows CDTW approximations without discretisations of any form. Our approximation algorithm is based on the fact that at least one of the paths $\gamma_{xy}$ and $\gamma_{yx}$ is a happy path whenever both $x$ and $y$ lie on borders of the cell $C$ . At first glance, it thus might even seem like simply omitting all unhappy paths in the propagation procedure of the exact algorithm from [5] yields a polynomial-time result for CDTW in 2D with approximation factor $\beta\leq 5$ . However, this is not the case because minimum-cost happy paths lack an important property of optimal paths: One can always choose non-crossing optimal paths (cf. [7, Lemma 11]), whereas minimum-cost happy paths may cross, e.g. as depicted in the final cell of Figure 1. This prevents the previously mentioned monotone assignment of quadratic pieces. To achieve a polynomial bound, we will propagate some unhappy paths while still keeping the resulting complexity low.

3.2 Algorithm Outline

Having established one of the main building blocks, we now provide a conceptual outline of our approximation algorithm, which uses a propagation scheme tailored to Definition 5 and Lemma 6. Although the outline has no requirements on the norm $\|\cdot\|$ , note that it only seems feasible to computationally deal with the propagated cost functions if they are well-behaved, such as under polygonal norms. We defer the implementation details along with the analysis to Section 4. The dynamic program in Algorithm 1 visits all parameter space cells in layers, starting at $C_{1,1}$ and ending at $C_{n,m}$ . For each cell $C$ we store its north, east, south and west border as $C.\mkern 2.0mu\mathcal{N}\mkern-2.0mu$ , $C.\mkern 1.0mu\mathcal{E}\mkern-1.0mu$ , $C.\mkern 1.0mu\mathcal{S}\mkern-1.0mu$ and $C.\mathcal{W}\mkern-1.0mu$ respectively. An output border $\mathcal{B}$ of $C$ knows its adjoining input border $\mathcal{B}.\mathrm{adj}$ and its opposing input border $\mathcal{B}.\mathrm{opp}$ . That means $C.\mkern 2.0mu\mathcal{N}\mkern-2.0mu.\mathrm{opp}:=C.\mkern 1.0mu\mathcal{S}% \mkern-1.0mu=:C.\mkern 1.0mu\mathcal{E}\mkern-1.0mu.\mathrm{adj}$ , so the first three cells of Figure 1 show paths between opposing borders, and the final two cells show the adjoining case. Symmetrically, we thus have $C.\mkern 2.0mu\mathcal{N}\mkern-2.0mu.\mathrm{adj}:=C.\mathcal{W}\mkern-1.0mu=% :C.\mkern 1.0mu\mathcal{E}\mkern-1.0mu.\mathrm{opp}$ as well. (Cf. [5, Definition 13].)

Our algorithm computes for every cell border $\mathcal{B}$ a cost function $\mathcal{B}.\mathrm{apx}$ that $5$ -approximates the optimum function $\mathrm{opt}_{0,\mathcal{B}}$ . We also store a value $h_{i,j}$ for all $(i,j)\in\{0,\dotsc,n\}\times\{0,\dotsc,m\}$ , which is set to the minimum computed cost from $\mathbf{0}$ to the north-east corner $(\|P_{\leq i}\|,\|Q_{\leq j}\|)^{\mathsf{T}}$ of the cell $C_{i,j}$ . The base case of the dynamic program in lines 1–2 is as usual: It initialises all costs given by paths that travel either straight horizontally or straight vertically from $\mathbf{0}$ . Then the main loop initialises in lines 6–7 for each cell $C$ the approximate cost functions of its output borders $C.\mkern 2.0mu\mathcal{N}\mkern-2.0mu$ and $C.\mkern 1.0mu\mathcal{E}\mkern-1.0mu$ via straight paths from the cell corners.

Algorithm 1 A

5

-approximation for CDTW of polygonal curves

P, Q

in

(\mathbb{R}^{2},\mbox{$\|\cdot\|$})

.

In the following, the costs of optimal paths within $C$ are implicitly given by some choice of $\ell$ as in Theorem 4. Next, lines 8–11 of Algorithm 1 identify the best path from each of the two input borders to the north-east corner of $C$ . See 3(a) for a possible configuration. Our propagation scheme utilises these paths’ costs and starting points, which are passed to the subroutine $C.\hyperref@@ii[alg:propagate-costs]{\textsc{PropagateCosts}}$ . This is a difference to previous propagation-based CDTW algorithms [15, 7, 2, 5], although a related idea was stated in [6, Observation 3.3] within the context of the partial Fréchet similarity.

(a) Best paths from input borders to corner

\mathcal{NE}

.

(b) Propagation from border

\mathcal{W}

to border

\mathcal{N}

.

(c) Propagation from border

\mathcal{S}

to border

\mathcal{E}

.

(d) Final result after propagating

\mathcal{S}

to

\mathcal{N}

.

Figure 3: Example of algorithm steps in case of

\min H_{\mathcal{S}}=h^{*}_{\mathcal{S}}<h^{*}_{\mathcal{W}}=\min H_{\mathcal{% W}}

.

As outlined in Algorithm 2, every input border $\mathcal{A}$ of $C$ is then propagated to its adjoining output border $\mathcal{B}$ using the subroutine $\mathcal{B}.\hyperref@@ii[alg:propagate-from-adj]{\textsc{% PropagateFromAdjoining}}$ , which updates the cost function $\mathcal{B}.\mathrm{apx}$ . It only propagates paths with the same starting point on $\mathcal{A}$ as its best path to the north-east corner, see 3(b). This may include unhappy paths with that starting point, e.g. as in 3(c), but it omits all other unhappy paths in contrast to exact algorithms. In a final step, at most one input border $\mathcal{A}$ is propagated to its opposing output border $\mathcal{B}$ , namely if its best path to the north-east corner is better than the other one. Here, $\mathcal{B}.\hyperref@@ii[alg:propagate-from-opp]{\textsc{% PropagateFromOpposing}}$ updates $\mathcal{B}.\mathrm{apx}$ by computing a lower envelope over all points located on $\mathcal{A}$ up to its best path’s starting point. See 3(d) for an example result.

Algorithm 2 Subroutines for propagating costs from input to output borders.

4 Algorithm Analysis and Specifics

In Section 4.1 we show that the above algorithm outline gives a $5$ -approximation for CDTW. Its implementation details and the resulting running time depend on the (polygonal) norm $\|\cdot\|$ . We first consider $\|\cdot\|_{1}$ in Section 4.2 and afterwards extend our results in Section 4.3. Both the proof of approximation factor and the running time analysis build upon the fact that all approximate cost functions computed by our algorithm are continuous. To show that, one can apply a useful lemma, which says that converging paths have converging costs.

Lemma 8 ([5, Lemma 19]).

Let $\gamma$ be an arbitrary $(x,y)$ -path, and let $(\gamma_{k})_{k\in\mathbb{N}}$ be a sequence of $(x_{k},y_{k})$ -paths converging to $\gamma$ , which means $\lim_{k\to\infty}(x_{k},y_{k})=(x,y)$ and $\lim_{k\to\infty}\gamma_{k}(\lambda)=\gamma(\lambda)$ for all $\lambda\in(\|x\|_{1},\|y\|_{1})$ . The limit $\lim_{k\to\infty}\mathrm{cost}_{\|\cdot\|}(\gamma_{k})$ exists and is equal to $\mathrm{cost}_{\|\cdot\|}(\gamma)$ .

Proposition 9.

For every border $\mathcal{B}$ the function $\mathcal{B}.\mathrm{apx}$ computed by our algorithm is continuous. Moreover, all $t,t^{\prime}\in\mathrm{dom}(\mathcal{B})$ with $t<t^{\prime}$ satisfy $\mathcal{B}.\mathrm{apx}(t)+\mathrm{opt}_{\|\cdot\|}(\mathcal{B}(t),\mathcal{B% }(t^{\prime}))\geq\mathcal{B}.\mathrm{apx}(t^{\prime})$ .

The proof of Proposition 9 is deferred to the full version. Showing the continuity of $\mathcal{B}.\mathrm{apx}$ through Lemma 8 is similar to the corresponding proof for the optimum function $\mathrm{opt}_{0,\mathcal{B}}$ [5, Theorem 20]. The second property implies that travelling on a border does not improve the computed costs, which justifies the use of the corner costs $h_{i-1,j},h_{i,j-1}$ in Algorithm 1.

4.1 Proof of Approximation Factor

We want to show that the cost of every optimal path from $\mathbf{0}$ to a cell border is $5$ -approximated. To that end, we give a formal and more general definition of best paths to a point. We also establish the existence of best paths and that they are closed under taking prefix paths.

Definition 10.

Let $\mathcal{A}$ be an input border of a cell $C$ , and let $y\in C$ be some point. A best path from $\mathcal{A}$ to $y$ is an optimal $(\mathcal{A}(s^{*}_{y}),y)$ -path $\gamma^{*}_{y}$ such that $s^{*}_{y}\in\mathrm{dom}(\mathcal{A})$ satisfies $\mathcal{A}(s^{*}_{y})\preceq y$ and minimises the function $s\mapsto\mathcal{A}.\mathrm{apx}(s)+\mathrm{opt}_{\|\cdot\|}(\mathcal{A}(s),y)$ . If the function value at $s^{*}_{y}$ is less than the analogous minimum for the other input border, we call $\gamma^{*}_{y}$ a dominating best path.

Lemma 11.

For each input border $\mathcal{A}$ of a cell $C$ and each point $y\in C$ there is a best path $\gamma^{*}_{y}$ from $\mathcal{A}$ to $y$ . Now let $\mathcal{A}(s^{*}_{y})$ with $s^{*}_{y}\in\mathrm{dom}(\mathcal{A})$ be the starting point of $\gamma^{*}_{y}$ , and let $\lambda\in[\lambda^{*}_{y},\|y\|_{1}]$ be arbitrary, where $\lambda^{*}_{y}:=\|\mathcal{A}(s^{*}_{y})\|_{1}$ . Then the prefix path $\gamma^{*}_{y}|_{[\lambda^{*}_{y},\lambda]}$ is a best path from $\mathcal{A}$ to $\gamma^{*}_{y}(\lambda)$ . If $\gamma^{*}_{y}$ is dominating, we have that $\gamma^{*}_{y}|_{[\lambda^{*}_{y},\lambda]}$ is dominating as well.

Proof.

Consider the function $s\mapsto\mathcal{A}.\mathrm{apx}(s)+\mathrm{opt}_{\|\cdot\|}(\mathcal{A}(s),y)$ from Definition 10. By Proposition 9, $\mathcal{A}.\mathrm{apx}$ is continuous. Lemma 8 and Theorem 4 imply that $s\mapsto\mathrm{opt}_{\|\cdot\|}(\mathcal{A}(s),y)$ is also continuous. Basic calculus says that their sum is a continuous function attaining its minimum on the closed interval $\{s\in\mathrm{dom}(\mathcal{A})\mid\mathcal{A}(s)\preceq y\}$ at some $s^{*}_{y}$ .

If any prefix path $\gamma^{*}_{y}|_{[\lambda^{*}_{y},\lambda]}$ of an optimal $(\mathcal{A}(s^{*}_{y}),y)$ -path $\gamma^{*}_{y}$ were not a best path, there would be a better path $\gamma_{\lambda}$ from $\mathcal{A}$ to $\gamma^{*}_{y}(\lambda)$ . Concatenating $\gamma_{\lambda}$ with the suffix of $\gamma^{*}_{y}$ would yield a better path from $\mathcal{A}$ to $y$ than $\gamma^{*}_{y}$ , a contradiction. Similarly, the existence of a non-dominating prefix path of $\gamma^{*}_{y}$ would imply that $\gamma^{*}_{y}$ is non-dominating. $\hfill\blacktriangleleft$

This enables us to show that for paths whose costs are not propagated by the subroutines from Algorithm 2 there are propagations of paths with better or approximating costs. In case of opposing borders, we always find better paths and thus do not require any approximations.

Proposition 12.

Let $\mathcal{B}$ be an output border of a cell $C$ with opposing input border $\mathcal{A}:=\mathcal{B}.\mathrm{opp}$ . It is $\mathcal{B}.\mathrm{apx}(t)\leq\mathcal{A}.\mathrm{apx}(s)+\mathrm{opt}_{% \mathcal{A},\mathcal{B}}(s,t)$ for all $(s,t)\in\mathrm{dom}(\mathcal{A})\times\mathrm{dom}(\mathcal{B})$ with $s\leq t$ .

Proof.

Let $\gamma$ be an optimal $(\mathcal{A}(s),\mathcal{B}(t))$ -path. We next distinguish between whether the subroutine $\mathcal{B}.\hyperref@@ii[alg:propagate-from-opp]{\textsc{% PropagateFromOpposing}}$ from Algorithm 2 is called for the given border $\mathcal{B}$ or not. Assume first that it is called. If $s\leq s^{*}$ holds, where $s^{*}:=\arg\min H_{\mathcal{A}}$ is given by lines 8–10 of Algorithm 1, then this call yields $\mathcal{B}.\mathrm{apx}(t)\leq\mathrm{apx}_{\leq s^{*}}(t)\leq\mathcal{A}.% \mathrm{apx}(s)+\mathrm{opt}_{\mathcal{A},\mathcal{B}}(s,t)$ . Else, we have $s>s^{*}$ and it follows that $\gamma$ intersects a best path $\gamma^{*}$ from $\mathcal{A}$ to the north-east corner of $C$ in some point $z\in C$ , see 4(a). Lemma 11 says $\mathcal{A}.\mathrm{apx}(s^{*})+\mathrm{opt}_{\|\cdot\|}(\mathcal{A}(s^{*}),z)% \leq\mathcal{A}.\mathrm{apx}(s)+\mathrm{opt}_{\|\cdot\|}(\mathcal{A}(s),z)$ , so that the call yields

\mathcal{B}.\mathrm{apx}(t)\leq\mathrm{apx}_{\leq s^{*}}(t)\leq\mathcal{A}.% \mathrm{apx}(s^{*})+\mathrm{opt}_{\mathcal{A},\mathcal{B}}(s^{*},t)\leq% \mathcal{A}.\mathrm{apx}(s)+\mathrm{opt}_{\mathcal{A},\mathcal{B}}(s,t)\text{.}

Assume now that $\mathcal{B}.\hyperref@@ii[alg:propagate-from-opp]{\textsc{% PropagateFromOpposing}}$ is not called. Because of the decisions made in lines 4–5 of Algorithm 2, there necessarily exists a dominating best path $\gamma^{*}_{0}$ from the other input border $\mathcal{A}_{0}:=\mathcal{B}.\mathrm{adj}$ to the north-east corner of $C$ . The path $\gamma^{*}_{0}$ intersects all paths from $\mathcal{A}$ to $\mathcal{B}$ , including $\gamma$ . Let $z_{0}\in C$ be an intersection point of these two paths, and let $\mathcal{A}_{0}(s^{*}_{0})$ be the starting point of $\gamma^{*}_{0}$ . Lemma 11 says $\mathcal{A}_{0}.\mathrm{apx}(s^{*}_{0})+\mathrm{opt}_{\|\cdot\|}(\mathcal{A}_{% 0}(s^{*}_{0}),z_{0})<\mathcal{A}.\mathrm{apx}(s)+\mathrm{opt}_{\|\cdot\|}(% \mathcal{A}(s),z_{0})$ . Hence, the subroutine call $\mathcal{A}_{0}.\hyperref@@ii[alg:propagate-from-adj]{\textsc{% PropagateFromAdjoining}}$ , which occurs in lines 2–3 of Algorithm 2, now results in

\mathcal{B}.\mathrm{apx}(t)\leq\mathrm{apx}_{s^{*}_{0}}(t)=\mathcal{A}_{0}.% \mathrm{apx}(s^{*}_{0})+\mathrm{opt}_{\mathcal{A}_{0},\mathcal{B}}(s^{*}_{0},t% )<\mathcal{A}.\mathrm{apx}(s)+\mathrm{opt}_{\mathcal{A},\mathcal{B}}(s,t)\text% {.}\

$\hfill\blacktriangleleft$

In case of adjoining borders, we get a similar result for happy paths, whereas unhappy paths might not intersect any propagated best paths. We can, however, use Lemma 6 to show that all unhappy paths are already approximated by the propagation of the cell corner that is shared by the adjoining borders.

(a) Intersection with best path in case of opposing borders.

(b) Intersection with best path in case of adjoining borders.

(c) Approximation of unhappy path by cell corner path.

Figure 4: Different configurations yielding a path with at worst approximating cost.

Proposition 13.

Let $\mathcal{B}$ be an output border of a cell $C$ with adjoining input border $\mathcal{A}:=\mathcal{B}.\mathrm{adj}$ . It is $\mathcal{B}.\mathrm{apx}(t)\leq\mathcal{A}.\mathrm{apx}(s)+5\cdot\mathrm{opt}_% {\mathcal{A},\mathcal{B}}(s,t)$ for all $(s,t)\in\mathrm{dom}(\mathcal{A})\times\mathrm{dom}(\mathcal{B})$ .

Proof.

Let $\gamma$ be an optimal $(\mathcal{A}(s),\mathcal{B}(t))$ -path as in Theorem 4. Assume first that $\gamma$ is of the form from Theorem 4a. This implies that $\gamma$ intersects all paths from $\mathcal{A}$ to the north-east corner of $C$ , either on $\ell$ or otherwise like in 4(b). Let $\gamma^{*}$ be a best such path with starting point $\mathcal{A}(s^{*})$ , where $s^{*}:=\arg\min H_{\mathcal{A}}$ is given by lines 8–10 of Algorithm 1, and let $z\in C$ be an intersection point of $\gamma$ and $\gamma^{*}$ . Lemma 11 says $\mathcal{A}.\mathrm{apx}(s^{*})+\mathrm{opt}_{\|\cdot\|}(\mathcal{A}(s^{*}),z)% \leq\mathcal{A}.\mathrm{apx}(s)+\mathrm{opt}_{\|\cdot\|}(\mathcal{A}(s),z)$ . Thus, the call $\mathcal{B}.\hyperref@@ii[alg:propagate-from-adj]{\textsc{% PropagateFromAdjoining}}$ from lines 2–3 of Algorithm 2 results in $\mathcal{B}.\mathrm{apx}(t)\leq\mathrm{apx}_{s^{*}}(t)=\mathcal{A}.\mathrm{apx% }(s^{*})+\mathrm{opt}_{\mathcal{A},\mathcal{B}}(s^{*},t)\leq\mathcal{A}.% \mathrm{apx}(s)+\mathrm{opt}_{\mathcal{A},\mathcal{B}}(s,t)$ .

Assume now that $\gamma$ is of the form from Theorem 4b. By Lemma 6, we then have

\mathcal{A}.\mathrm{apx}(s)+5\cdot\mathrm{opt}_{\mathcal{A},\mathcal{B}}(s,t)=% \mathcal{A}.\mathrm{apx}(s)+5\cdot\mathrm{cost}_{\|\cdot\|}(\gamma)\geq% \mathcal{A}.\mathrm{apx}(s)+\mathrm{cost}_{\|\cdot\|}(\gamma_{c})\text{,}

where $\gamma_{c}$ is the $(\mathcal{A}(s),\mathcal{B}(t))$ -path through the shared cell corner $c=\mathcal{A}(s_{c})$ of the adjoining borders $\mathcal{A}$ and $\mathcal{B}$ , see 4(c). We obtain $\mathcal{A}.\mathrm{apx}(s)+\mathrm{cost}_{\|\cdot\|}(\gamma_{c})\geq\mathcal{% A}.\mathrm{apx}(s_{c})+\mathrm{opt}_{\|\cdot\|}(c,\mathcal{B}(t))\geq\mathcal{% B}.\mathrm{apx}(t)$ due to Proposition 9 and the initialisation of $\mathcal{B}.\mathrm{apx}$ in lines 6–7 of Algorithm 1. $\hfill\blacktriangleleft$

We conclude that the conceptual algorithm outline from Section 3.2 indeed gives a CDTW approximation within factor $\beta\leq 5$ . Using the above propositions, this follows by induction. See the full version for a proof of Theorem 14.

Theorem 14.

Any implementation of Algorithm 1 and Algorithm 2 under a norm $\|\cdot\|$ returns a factor- $5$ approximation of $\mathrm{cdtw}_{\|\cdot\|}(P,Q)$ for all polygonal curves $P, Q$ in $(\mathbb{R}^{2},\mbox{$\|\cdot\|$})$ .

As discussed in ▶ 7, we do not know whether the factor is tight. Even the value $\beta$ that is tight for Lemma 6 might not be tight for Theorem 14. It would only transfer if there are curves $P, Q$ with an optimal $(\mathbf{0},(\|P\|,\|Q\|)^{\mathsf{T}})$ -path that is predominantly unhappy.

4.2 Running Time under the 1-Norm

In this section we specify the details of how to implement our approximation algorithm under the $1$ -norm $\|\cdot\|_{1}$ , and analyse its running time on two curves $P, Q$ of complexity $n$ and $m$ respectively. By definition, we have $\|z\|_{1}=|z_{1}|+|z_{2}|$ for $z\in\mathbb{R}^{2}$ , meaning the $1$ -norm is linear on each quadrant of the plane. Every cell border $\mathcal{B}$ hence contains only $O(1)$ breakpoints where the function $t\mapsto\|P_{\|\cdot\|_{1}}(\mathcal{B}_{1}(t))-Q_{\|\cdot\|_{1}}(\mathcal{B}_% {2}(t))\|_{1}$ switches from one linear function piece to another. It follows that the base case in lines 1–2 of Algorithm 1, which uses straight paths, has piecewise linear integrands and yields $O(1)$ quadratic pieces on each initialised border $\mathcal{B}$ . Computing all pieces requires $O(n+m)$ time.

Similarly, propagating the costs of straight paths from the cell corners in lines 6–7 yields $O(1)$ initial quadratic pieces per output border of the cell $C$ . We now claim that lines 8–11 of Algorithm 1 take $O(N_{C.\mkern 1.0mu\mathcal{S}\mkern-1.0mu}+N_{C.\mathcal{W}\mkern-1.0mu})$ time, where $N_{\mathcal{B}}$ denotes the number of (maximal) quadratic pieces making up the computed cost function $\mathcal{B}.\mathrm{apx}$ of a border $\mathcal{B}$ . Note that the costs of optimal paths within $C$ are given by Theorem 4, and a suitable $\ell$ is computable in $O(1)$ time under $\|\cdot\|_{1}$ [5, Corollary 9]. First, we consider the possible starting points of best paths to the north-east corner of $C$ .

Definition 15.

Let $\mathcal{A},\mathcal{B}$ be a pair of input and output border, and let $(s_{0},t_{0})\in\mathrm{dom}(\mathcal{A})\times\mathrm{dom}(\mathcal{B})$ with $\mathcal{A}(s_{0})\preceq\mathcal{B}(t_{0})$ be arbitrary. If the function $s\mapsto\mathcal{A}.\mathrm{apx}(s)+\mathrm{opt}_{\mathcal{A},\mathcal{B}}(s,t% _{0})$ attains a semistrict ¹¹1That means strict to the left and/or to the right, ruling out interior points of constant-valued pieces. local minimum at $s_{0}$ , we say that $\mathcal{A}(s_{0})$ is a parent candidate for $\mathcal{B}(t_{0})$ . If $\mathcal{B}.\mathrm{apx}(t_{0})=\mathcal{A}.\mathrm{apx}(s_{0})+\mathrm{opt}_{% \mathcal{A},\mathcal{B}}(s_{0},t_{0})$ holds, we say that $\mathcal{A}(s_{0})$ is a parent point of $\mathcal{B}(t_{0})$ . We call an interval $S\subseteq\mathrm{dom}(\mathcal{A})$ a parent interval of $T\subseteq\mathrm{dom}(\mathcal{B})$ if each $\mathcal{B}(t)$ with $t\in T$ has a parent point $\mathcal{A}(s)$ with $s\in S$ .

This definition builds upon [7, Definition 18], but allows for a more fine-grained analysis: Whereas [7] collects consecutive quadratic pieces into specific subsegments and then introduces a parent relationship for these subsegments, we deal with arbitrary points and intervals.

For a fixed $t_{0}$ , as in lines 8–9 of Algorithm 1, the given function $s\mapsto\mathcal{A}.\mathrm{apx}(s)+\mathrm{opt}_{\mathcal{A},\mathcal{B}}(s,t% _{0})$ is piecewise quadratic with $N_{\mathcal{A}}+O(1)$ pieces under $\|\cdot\|_{1}$ . This is because $\mathcal{A}.\mathrm{apx}$ has $N_{\mathcal{A}}$ pieces, and the optimal $(\mathcal{A}(s),\mathcal{B}(t_{0}))$ -paths from Theorem 4 have $O(1)$ bending points whose coordinates may depend linearly on the variable $s$ . Hence, $s\mapsto\mathrm{opt}_{\mathcal{A},\mathcal{B}}(s,t_{0})$ has $O(1)$ quadratic pieces by the linearity of $\|\cdot\|_{1}$ on each quadrant. Basic calculus says that (semistrict) local minima of a piecewise quadratic function can only occur at domain endpoints, at breakpoints between pieces, or at points where the derivative is $0$ . The latter correspond to parabola vertices, see Figure 5.

Figure 5: Local minima of a continuous and piecewise quadratic function.

Overall, there are $O(N_{C.\mkern 1.0mu\mathcal{S}\mkern-1.0mu}+N_{C.\mathcal{W}\mkern-1.0mu})$ 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(N_{C.\mkern 1.0mu\mathcal{S}\mkern-1.0mu}+N_{C.\mathcal{W}\mkern-1.0mu})$ time under $\|\cdot\|_{1}$ . Moreover, we can reuse this candidate set for opposing propagation since parent points that do not share a coordinate with the child can be chosen from the same set. This is due to the following key lemma that pertains to happy optimal paths.

Lemma 16 (Happiness Lemma).

Let $X:=\{(s,t)\in S\times T\mid\mathcal{A}(s)\preceq\mathcal{B}(t)\}$ , where $\mathcal{A},\mathcal{B}$ is a pair of input and output border with $S\times T\subseteq\mathrm{dom}(\mathcal{A})\times\mathrm{dom}(\mathcal{B})$ . If all $(s,t)\in X$ have a happy optimal $(\mathcal{A}(s),\mathcal{B}(t))$ -path, it is $\mathrm{opt}_{\mathcal{A},\mathcal{B}}(s,t)=\rho_{\mathcal{A}}^{\;\!% \triangleright}(s)+\rho^{\mathcal{B}}_{\;\!\triangleright}(t)$ on $X$ for two univariate functions $\rho_{\mathcal{A}}^{\;\!\triangleright},\rho^{\mathcal{B}}_{\;\!\triangleright}$ . This always applies in case of $\mathcal{A}=\mathcal{B}.\mathrm{opp}$ and $S\times T=\mathrm{dom}(\mathcal{A})\times\mathrm{dom}(\mathcal{B})$ .

Proof.

The function $\mathrm{opt}_{\mathcal{A},\mathcal{B}}$ is obtained by evaluating costs of optimal $(\mathcal{A}(s),\mathcal{B}(t))$ -paths in terms of the parameter pair $(s,t)\in X$ , and we assume all paths given by Theorem 4 to be happy on $X$ . Consequently, each bending point $\xi_{0}$ lies on $\ell$ or on the cell’s boundary according to Definition 5. This implies that $\xi_{0}$ can be expressed in terms of only $s$ or in terms of only $t$ , cf. Figure 1. We evaluate optimal path costs by summing the costs of subpaths, each of which traces a line segment between two points $\xi$ and $\xi^{\prime}$ that are among $\mathcal{A}(s)$ , $\mathcal{B}(t)$ and the paths’ bending points. Definition 3 says that every such subpath cost is a definite integral of some function $\mbox{$\|\cdot\|$}\circ\psi$ on the interval $[\|\xi\|_{1},\|\xi^{\prime}\|_{1}]$ , where $\psi$ is an affine map. We distinguish the following two cases.

1.

If the traced line segment lies on $\ell$ or on the cell’s boundary, the corresponding function $\psi$ is fixed and does not depend on $s$ and $t$ . By the Fundamental Theorem of Calculus, the subpath cost is equal to $\Psi(\|\xi^{\prime}\|_{1})-\Psi(\|\xi\|_{1})$ , where $\Psi$ is an arbitrary antiderivative of the continuous integrand $\mbox{$\|\cdot\|$}\circ\psi$ . Due to happiness, the term $\Psi(\|\xi\|_{1})$ may depend only on $s$ and can thus be assigned to $\rho_{\mathcal{A}}^{\;\!\triangleright}$ , while $\Psi(\|\xi^{\prime}\|_{1})$ may depend only on $t$ and can be assigned to $\rho^{\mathcal{B}}_{\;\!\triangleright}$ .
2.

Otherwise, the traced segment is horizontal/vertical with $\xi=\mathcal{A}(s)$ or $\xi^{\prime}=\mathcal{B}(t)$ such that $\psi$ depends only on $s$ or only on $t$ . Then the other endpoint must depend on the same parameter, i.e. $\xi^{\prime}$ depends on $s$ or $\xi$ depends on $t$ . Due to happiness, it can be expressed in terms of only this parameter. The subpath cost can hence be assigned to $\rho_{\mathcal{A}}^{\;\!\triangleright}$ or $\rho^{\mathcal{B}}_{\;\!\triangleright}$ respectively.

It remains to show that every $(x,y)$ -path $\gamma$ for $x, y$ on opposing borders is happy. Since paths from Theorem 4a are always happy, we assume that $\gamma$ is as in Theorem 4b and consider the single breaking point $\xi$ of $\gamma$ . By construction, $\xi$ shares one coordinate value with $x$ and another with $y$ . Opposing borders parametrise via the same coordinate and keep the other fixed, cf. Definition 2. It follows that the value of $\xi$ in the non-parametric coordinate is equal to one border’s fixed value. This means that $\xi$ lies on the related border and thus on the boundary of $C$ , so $\gamma$ is happy. $\hfill\blacktriangleleft$

Being able to split costs into two univariate functions simplifies the behaviour of local minima in terms of one variable, which yields the desired characterisation of parent candidates.

Proposition 17.

Let $\mathcal{A}$ be an input border of a cell $C$ , and let $S^{*}_{\mathcal{A}}$ be defined as follows:

S^{*}_{\mathcal{A}}:=\{s\in\mathrm{dom}(\mathcal{A})\mid\mathcal{A}(s)\text{ % is a parent candidate for the north-east corner of }C\}\text{.}

Let $t_{0}\in\mathrm{dom}(\mathcal{B})$ , where $\mathcal{B}$ is the opposing output border of $\mathcal{A}$ . For every $s\in S^{*}_{\mathcal{A}}$ with $s\leq t_{0}$ we have that $\mathcal{A}(s)$ is a parent candidate for $\mathcal{B}(t_{0})$ . Conversely, each parent candidate $\mathcal{A}(s_{0})$ for $\mathcal{B}(t_{0})$ satisfies $s_{0}\in\{s\in S^{*}_{\mathcal{A}}\mid s\leq t_{0}\}\cup\{t_{0}\}$ . It is $|S^{*}_{\mathcal{A}}|\in O(N_{\mathcal{A}})$ under $\|\cdot\|_{1}$ .

Proof.

We start with the bound for $|S^{*}_{\mathcal{A}}|$ under $\|\cdot\|_{1}$ . As argued above, for a fixed $t_{0}\in\mathrm{dom}(\mathcal{B})$ the function $s\mapsto\mathcal{A}.\mathrm{apx}(s)+\mathrm{opt}_{\mathcal{A},\mathcal{B}}(s,t% _{0})$ from Definition 15 is piecewise quadratic with $N_{\mathcal{A}}+O(1)$ pieces under $\|\cdot\|_{1}$ . Apart from domain endpoints and piece breakpoints, each piece can contribute at most one semistrict local minimum with derivative $0$ , so we have $|S^{*}_{\mathcal{A}}|\in O(N_{\mathcal{A}})$ . In general, we have $\mathcal{A}.\mathrm{apx}(s)+\mathrm{opt}_{\mathcal{A},\mathcal{B}}(s,t_{0})=% \mathcal{A}.\mathrm{apx}(s)+\rho_{\mathcal{A}}^{\;\!\triangleright}(s)+\rho^{% \mathcal{B}}_{\;\!\triangleright}(t_{0})$ for all $s\in\mathrm{dom}(\mathcal{A})$ with $s\leq t_{0}$ , where $\rho_{\mathcal{A}}^{\;\!\triangleright},\rho^{\mathcal{B}}_{\;\!\triangleright}$ are as in Lemma 16. Because $\rho^{\mathcal{B}}_{\;\!\triangleright}(t_{0})$ does not depend on the variable $s$ , all local minima that the function attains on the interior of its domain are entirely determined by $\mathcal{A}.\mathrm{apx}$ and $\rho_{\mathcal{A}}^{\;\!\triangleright}$ . The same applies to the fixed left endpoint of the domain, while the right endpoint is exactly $t_{0}$ per the constraint $s\leq t_{0}$ of monotone paths. Hence, it is the only parent candidate that can vary. The north-east corner of $C$ gives the largest domain, so the stated results follow. $\hfill\blacktriangleleft$

The intuition behind $s_{0}\in S^{*}_{\mathcal{A}}$ versus $s_{0}=t_{0}$ for opposing propagation is that the corresponding paths may switch between the two types depicted in the second cell of Figure 1: Either they are straight with $s_{0}=t_{0}$ , or they travel on $\ell$ after starting at a point $\mathcal{A}(s_{0})$ with $s_{0}\in S^{*}_{\mathcal{A}}$ . In fact, this switching is a major reason behind the $O((n+m)^{5})$ time complexity of the exact 1D algorithm [7]. Note that in 1D the CDTW integrand is $0$ everywhere on $\ell$ . The procedure from [7] propagates from $\mathcal{A}$ to $\ell$ , performs a cumulative minimum operation on $\ell$ , and then propagates from $\ell$ to $\mathcal{B}$ . In 2D a cell $C$ is generally associated with two non-parallel curve segments, so that the CDTW integrand is non-zero within $C$ except at the point that corresponds to their intersection. Although the cumulative minimum operation can be adapted to non-zero weightings (cf. [7, Observation 46]), Lemma 16 reveals the underlying principles and generalises them to all happy paths. This technical contribution of ours advances the understanding of function propagations. It allows us to streamline and enhance the running time analysis compared to [7], yet it does not hold for unhappy paths. Their propagation complexity is still unknown in 2D, see [5, Section 4.2].

We now continue with the implementation of the subroutines from Algorithm 2 under the $1$ -norm $\|\cdot\|_{1}$ . In $\mathcal{B}.\hyperref@@ii[alg:propagate-from-adj]{\textsc{% PropagateFromAdjoining}}$ the function $\mathcal{B}.\mathrm{apx}$ gets updated through taking its lower envelope with the function $\mathrm{apx}_{s^{*}}$ defined by $t\mapsto\mathcal{A}.\mathrm{apx}(s^{*})+\mathrm{opt}_{\mathcal{A},\mathcal{B}}% (s^{*},t)$ on $\mathrm{dom}(\mathcal{B})$ . The given value $s^{*}$ provides a fixed starting point for propagated paths, which may include unhappy paths. As fixing the first argument of $\mathrm{opt}_{\mathcal{A},\mathcal{B}}$ is symmetric to fixing its second argument, we have that the function $\mathrm{apx}_{s^{*}}$ is piecewise quadratic with $O(1)$ pieces under $\|\cdot\|_{1}$ . Moreover, $\mathcal{B}.\mathrm{apx}$ has $O(1)$ pieces before the subroutine calls in lines 2–3 of Algorithm 2 occur, so taking the lower envelope requires finding only a constant number of intersections between pieces as in Figure 7.

Figure 6: Intersection between
piecewise quadratic functions.

Figure 7: Monotone assignment of
intervals on

\mathcal{B}

to parents on

\mathcal{A}

.

In $\mathcal{B}.\hyperref@@ii[alg:propagate-from-opp]{\textsc{% PropagateFromOpposing}}$ the cost function $\mathcal{B}.\mathrm{apx}$ then gets updated through taking its lower envelope with the function $\mathrm{apx}_{\leq s^{*}}$ defined by $t\mapsto\min_{s\leq s^{*}\land s\leq t}\mathcal{A}.\mathrm{apx}(s)+\mathrm{opt% }_{\mathcal{A},\mathcal{B}}(s,t)$ on $\mathrm{dom}(\mathcal{B})$ . The function $\mathrm{apx}_{\leq s^{*}}$ is itself a lower envelope, and Proposition 17 implies that it is covered by optimal paths starting at the parent candidates from $\{s\in S^{*}_{\mathcal{A}}\mid s\leq s^{*}\}$ together with straight paths starting before $\mathcal{A}(s^{*})$ . The costs of the former paths are given by $O(N_{\mathcal{A}})$ functions under $\|\cdot\|_{1}$ , each of which again has $O(1)$ quadratic pieces. The latter paths’ costs are given by the function $t\mapsto\mathcal{A}.\mathrm{apx}(t)+\mathrm{opt}_{\mathcal{A},\mathcal{B}}(t,t)$ for $t\leq s^{*}$ , which has at most $N_{\mathcal{A}}+O(1)$ pieces.

The lower envelope of these pieces with the existing $O(1)$ pieces on $\mathcal{B}$ is computable in linear time since the new pieces are given monotonically by parent points. Those induce intervals on $\mathcal{B}$ that have parent intervals on $\mathcal{A}$ separated by $S^{*}_{\mathcal{A}}$ , see Figure 7. We traverse $\mathcal{A}$ in ascending order, and compare pieces on $\mathcal{B}$ given by the current and an earlier interval on $\mathcal{A}$ . In contrast to previous algorithms [7, 5], we do a single bottom-up pass on $\mathcal{B}$ instead of repeated top-down passes. As it takes $O(N_{\mathcal{A}})$ time to perform an opposing propagation under $\|\cdot\|_{1}$ with this method, lines 8–11 of Algorithm 1 take $O(N_{C.\mkern 1.0mu\mathcal{S}\mkern-1.0mu}+N_{C.\mathcal{W}\mkern-1.0mu})$ time in total. We can sum this bound over all cells.

Lemma 18.

Let $t_{0}\in\mathrm{dom}(\mathcal{B})$ for an output border $\mathcal{B}$ with opposing input border $\mathcal{A}:=\mathcal{B}.\mathrm{opp}$ , and let $\mathcal{A}(s_{0})$ be the starting point of a best path from $\mathcal{A}$ to $\mathcal{B}(t_{0})$ with smallest $s_{0}$ . It is

\mathcal{A}.\mathrm{apx}(s_{0})+\mathrm{opt}_{\mathcal{A},\mathcal{B}}(s_{0},t% )<\mathcal{A}.\mathrm{apx}(s)+\mathrm{opt}_{\mathcal{A},\mathcal{B}}(s,t)\quad% \text{whenever }s<s_{0}\leq t\text{.}

In particular, for all $t\geq s_{0}$ we have that every parent point $\mathcal{A}(s)$ of $\mathcal{B}(t)$ satisfies $s\geq s_{0}$ .

Proof.

Because $\mathcal{A}(s_{0})$ is the starting point of a best path to $\mathcal{B}(t_{0})$ , Definition 10 says $\mathcal{A}.\mathrm{apx}(s_{0})+\mathrm{opt}_{\mathcal{A},\mathcal{B}}(s_{0},t% _{0})\leq\mathcal{A}.\mathrm{apx}(s)+\mathrm{opt}_{\mathcal{A},\mathcal{B}}(s,% t_{0})$ for all $s\leq t_{0}$ . If $s<s_{0}$ , this holds with strict inequality since there is no such point $\mathcal{A}(s)$ by choice of $s_{0}$ as the smallest possible value. Using Lemma 16 therefore gives $\mathcal{A}.\mathrm{apx}(s_{0})+\rho_{\mathcal{A}}^{\;\!\triangleright}(s_{0})% +\rho^{\mathcal{B}}_{\;\!\triangleright}(t_{0})<\mathcal{A}.\mathrm{apx}(s)+% \rho_{\mathcal{A}}^{\;\!\triangleright}(s)+\rho^{\mathcal{B}}_{\;\!% \triangleright}(t_{0})$ for all $s<s_{0}$ . By subtracting $\rho^{\mathcal{B}}_{\;\!\triangleright}(t_{0})$ from that inequality, adding $\rho^{\mathcal{B}}_{\;\!\triangleright}(t)$ for a $t\geq s_{0}$ , and using Lemma 16 once more, we get $\mathcal{A}.\mathrm{apx}(s_{0})+\mathrm{opt}_{\mathcal{A},\mathcal{B}}(s_{0},t% )<\mathcal{A}.\mathrm{apx}(s)+\mathrm{opt}_{\mathcal{A},\mathcal{B}}(s,t)$ for all $s<s_{0}$ as desired. Thus, there is no parent point $\mathcal{A}(s)$ of $\mathcal{B}(t)$ with $s<s_{0}$ due to Proposition 12. $\hfill\blacktriangleleft$

Proposition 19.

Let $\mathcal{B}$ be an output border with opposing input border $\mathcal{A}:=\mathcal{B}.\mathrm{opp}$ . We can perform $\mathcal{B}.\hyperref@@ii[alg:propagate-from-opp]{\textsc{% PropagateFromOpposing}}$ in $O(N_{\mathcal{A}})$ time under $\|\cdot\|_{1}$ . Algorithm 1 then has a running time in $O(N)$ , where $N$ is the total number of quadratic pieces over all cell borders.

Proof.

In the following, we describe a procedure that computes the lower envelope $\mathrm{apx}_{\leq s^{*}}$ for the subroutine, where $s^{*}\in\mathrm{dom}(\mathcal{A})$ is the value passed to its call. Let $s^{*}_{1},\dotsc,s^{*}_{\lambda}$ be the elements of the set $\{s\in S^{*}_{\mathcal{A}}\mid s\leq s^{*}\}$ in ascending order, where $S^{*}_{\mathcal{A}}$ is as in Proposition 17. We have w.l.o.g. that the inclusion $s^{*}\in S^{*}_{\mathcal{A}}$ holds, which further implies $s^{*}_{\lambda}=s^{*}$ . This is since $s^{*}$ gives a global and thus also a local minimum: Its computation in lines 8–10 of Algorithm 1 and the decisions made in lines 4–5 of Algorithm 2 mean $\mathcal{A}(s^{*})$ is a parent point of the north-east cell corner.

We partition the interval $\{s\in\mathrm{dom}(\mathcal{A})\mid s\leq s^{*}_{\lambda}\}$ , which contains all starting points considered by $\mathrm{apx}_{\leq s^{*}}$ , into subintervals $S_{1}:=\{s\in\mathrm{dom}(\mathcal{A})\mid s\leq s^{*}_{1}\}$ and $S_{\kappa}:=(s^{*}_{\kappa-1},s^{*}_{\kappa}]$ for $\kappa\in\{2,\dotsc,\lambda\}$ . Given a subset $T_{\kappa}\subseteq\mathrm{dom}(\mathcal{B})$ with parent interval $S_{\kappa}$ for any $\kappa\in\{1,\dotsc,\lambda\}$ , Proposition 17 implies that the pieces of $\mathrm{apx}_{\leq s^{*}}$ on $T_{\kappa}$ are those of the function $\tau_{\kappa}$ defined by $t\mapsto\mathcal{A}.\mathrm{apx}(t)+\mathrm{opt}_{\mathcal{A},\mathcal{B}}(t,t)$ for $t\in S_{\kappa}$ and $t\mapsto\mathcal{A}.\mathrm{apx}(s^{*}_{\kappa})+\mathrm{opt}_{\mathcal{A},% \mathcal{B}}(s^{*}_{\kappa},t)$ for $t>s^{*}_{\kappa}$ . See Figure 7 for an example. To compute the lower envelope of $\tau_{1},\dotsc,\tau_{\lambda}$ , it is not necessary to create all pieces of these functions. Instead, we traverse $S_{1},\dotsc,S_{\lambda}$ and create pieces on the fly through maintaining an active function.

Initially, $\tau_{1}$ is active on all of $S_{1}$ . For $\kappa\in\{2,\dotsc,\lambda\}$ we compare the restriction $\tau_{\kappa}|_{S_{\kappa}}$ with the yet active function $\tau_{\mu}$ by checking their overlapping pairs of pieces for intersections as in Figure 7. This takes $O(1)$ time per pair. If $\tau_{\mu}$ is nowhere greater than $\tau_{\kappa}$ on $S_{\kappa}$ , then $\tau_{\mu}$ remains active there. Otherwise, $\tau_{\mu}$ only stays active up to the earliest point after which $\tau_{\kappa}$ is smaller. At this point $\tau_{\kappa}$ becomes active and stays so on the remainder of $S_{\kappa}$ . After $S_{\lambda}$ has been processed, the traversal is complete and the last active function $\tau_{\mu}$ stays so on the remaining part of the domain.

This procedure correctly constructs the lower envelope: Let $\mathcal{A}(s_{0})$ be the earliest starting point of a best path to an arbitrary point $\mathcal{B}(t_{0})$ , and let $\kappa\in\{1,\dotsc,\lambda\}$ with $s_{0}\in S_{\kappa}$ . By Proposition 17, all sets of parent candidates are finite. Hence, Lemma 18 and continuity of $s\mapsto\mathcal{A}.\mathrm{apx}(s)+\mathrm{opt}_{\mathcal{A},\mathcal{B}}(s,t)$ , cf. the proof of Lemma 11, imply that each $t\geq s_{0}$ has a smallest $s_{t}\in[s_{0},t]$ such that $\mathcal{A}(s_{t})$ is a parent candidate for $\mathcal{B}(t)$ . Together with the definition of $S_{\kappa}$ , we get $\tau_{\kappa}(t)=\mathcal{A}.\mathrm{apx}(s_{t})+\mathrm{opt}_{\mathcal{A},% \mathcal{B}}(s_{t},t)\leq\mathcal{A}.\mathrm{apx}(s_{0})+\mathrm{opt}_{% \mathcal{A},\mathcal{B}}(s_{0},t)<\min\{\tau_{1}(t),\dotsc,\tau_{\kappa-1}(t)\}$ for all $t\geq s_{0}$ , while $\tau_{\kappa}$ becomes active.

Furthermore, at most $N_{\mathcal{A}}+O(|S^{*}_{\mathcal{A}}|)$ overlapping pairs of pieces are created under $\|\cdot\|_{1}$ , which yields a running time in $O(N_{\mathcal{A}})$ by Proposition 17. This is because $\tau_{1}|_{S_{1}},\dotsc,\tau_{\lambda}|_{S_{\lambda}}$ together have at most $N_{\mathcal{A}}+|S^{*}_{\mathcal{A}}|+O(1)$ pieces, and we create at most $|S^{*}_{\mathcal{A}}|+O(1)$ pieces of $\tau_{\mu}|_{S_{\kappa}}$ with $\mu<\kappa$ over all active $\tau_{\mu}$ due to the starting points then being fixed to $s^{*}_{\mu}$ . It remains to update $\mathcal{B}.\mathrm{apx}$ , which already contains $O(1)$ pieces, through taking its lower envelope with the pieces of $\mathrm{apx}_{\leq s^{*}}$ in $O(N_{\mathcal{A}})$ time.²²2Alternatively to updating $\mathcal{B}.\mathrm{apx}$ at the end, one can instead construct an initial active function $\tau_{0}$ using its existing pieces, and start comparisons on $S_{1}$ . (Due to the separation of pieces that is explained in the proof of Lemma 24). Altogether, we perform $\mathcal{B}.\hyperref@@ii[alg:propagate-from-opp]{\textsc{% PropagateFromOpposing}}$ in $O(N_{\mathcal{A}})$ time, so that Algorithm 1 takes $O(N_{C.\mkern 1.0mu\mathcal{S}\mkern-1.0mu}+N_{C.\mathcal{W}\mkern-1.0mu})$ time per cell $C$ by what has been argued above in this section. Summing this bound over all cells finally yields a total running time in $O(N)$ under $\|\cdot\|_{1}$ . $\hfill\blacktriangleleft$

The central challenge is to bound the number $N$ polynomially in the complexities $n, m$ of the input curves. As indicated by the above proof, Lemma 18 implies $N_{\mathcal{B}}\leq N_{\mathcal{A}}+O(|S^{*}_{\mathcal{A}}|)$ under $\|\cdot\|_{1}$ , but combining that with $|S^{*}_{\mathcal{A}}|\in O(N_{\mathcal{A}})$ from Proposition 17 is still too weak. It cannot rule out an exponential growth since it allows constants $c>1$ with $N_{\mathcal{B}}\geq c\cdot N_{\mathcal{A}}$ . This necessitates a better bound for $|S^{*}_{\mathcal{A}}|$ that does not depend on $N_{\mathcal{A}}$ . We show that $|S^{*}_{\mathcal{A}}|$ grows at worst quadratically over successive propagations between opposing borders. The resulting inductive bound for $N_{\mathcal{B}}$ is our main ingredient for establishing that $N$ is polynomial.

Definition 20.

We assign each border $\mathcal{B}$ a rank. If $\mathcal{B}.\hyperref@@ii[alg:propagate-from-opp]{\textsc{% PropagateFromOpposing}}$ is not called for $\mathcal{B}$ , it has rank $0$ . Else, it has rank $r:=r_{0}+1$ , where $r_{0}\in\mathbb{N}_{0}$ is the rank of $\mathcal{B}.\mathrm{opp}$ .

Lemma 21.

Let $\mathcal{B}$ be an output border of rank $r>0$ with opposing input border $\mathcal{A}:=\mathcal{B}.\mathrm{opp}$ . Then the number $N_{\mathcal{B}}$ is bounded by $N_{\mathcal{B}}\leq N_{\mathcal{A}}+O(|S^{*}_{\mathcal{A}}|)$ with $|S^{*}_{\mathcal{A}}|\in O(r^{2})$ under $\|\cdot\|_{1}$ .

Lemma 21 follows from the more general Lemma 24 that we will prove below in Section 4.3. In comparison to [7, Lemma 14], the proof of our bounds avoids a distinction between different types of subsegments. It instead uses the Happiness Lemma to implicitly handle all types that are relevant for our algorithm. With these bounds in place, it remains to count the number of quadratic pieces on a border as well as the number of borders for each rank.

Proposition 22.

In a parameter space with $n\times m$ cells the ranks are at most $\max\{n,m\}$ . There are $O(nm)$ borders of rank $0$ , each of which has $O(1)$ quadratic pieces under $\|\cdot\|_{1}$ . There are $O(nm/r)$ borders of any rank $r>0$ , each of which has $O(r^{3})$ pieces under $\|\cdot\|_{1}$ .

Proof.

The first claim is true since ranks can only accumulate along a row or column of cells by Definition 20. As there are $O(nm)$ borders in total, this particularly holds for borders of rank $0$ , and we have already argued in this section that these borders have $O(1)$ pieces under $\|\cdot\|_{1}$ . Each border $\mathcal{B}$ of rank $r>0$ has $r$ predecessor borders of ranks $0,\dotsc,r-1$ that are disjoint from all the other predecessors, so the number of rank- $r$ borders is in $O(nm/r)$ . Finally, we show $N_{\mathcal{B}}\leq c^{2}\cdot r^{3}$ by induction, where $c\in\mathbb{N}$ is a universal constant for the bounds of Lemma 21. In the base case for $r=1$ , only one propagation from a border of rank $0$ with $O(1)$ pieces has occurred. For the inductive step we assume $r=r_{0}+1$ , where $r_{0}>0$ is the rank of $\mathcal{A}:=\mathcal{B}.\mathrm{opp}$ . By using Lemma 21 and the induction hypothesis for $\mathcal{A}$ , we get

N_{\mathcal{B}}\leq N_{\mathcal{A}}+c\cdot|S^{*}_{\mathcal{A}}|\leq c^{2}\cdot r% _{0}^{3}+c\cdot(c\cdot r^{2})\leq c^{2}\cdot r^{2}(r_{0}+1)=c^{2}\cdot r^{3}% \text{.}\

$\hfill\blacktriangleleft$

When putting it together, we assume $n\geq m$ in order to bound the maximum rank by $n$ . This is not a restriction since the input curves $P, Q$ can be swapped: We have $\mathrm{cdtw}_{\|\cdot\|}(P,Q)=\allowbreak\mathrm{cdtw}_{\|\cdot\|}(Q,P)$ under any norm $\|\cdot\|$ , as Definition 1 inherits the norm-induced symmetry.

Theorem 23.

Given polygonal curves $P=\langle p_{0},\dotsc,p_{n}\rangle$ and $Q=\langle q_{0},\dotsc,q_{m}\rangle$ in $(\mathbb{R}^{2},\mbox{$\|\cdot\|_{1}$})$ , where $n\geq m$ , our $5$ -approximation for CDTW of $P, Q$ under $\|\cdot\|_{1}$ takes $O(n^{4}m)$ time.

Proof.

Proposition 19 says that the running time is linear in $N$ . By Proposition 22, there is a constant $c\in\mathbb{N}$ with $N\leq c\cdot(nm+\sum_{r=1}^{n}nm/r\cdot r^{3})=c\cdot nm\cdot(1+\sum_{r=1}^{n}% r^{2})\leq 2c\cdot n^{4}m$ . $\hfill\blacktriangleleft$

4.3 Extension to Other Norms

We proceed to extend the above implementation and running time analysis of our algorithm from the $1$ -norm to general polygonal norms, which we will subsequently use in order to approximate any given norm on $\mathbb{R}^{2}$ such as the $2$ -norm. For these purposes, we employ the following characterisation: A function is a norm on $\mathbb{R}^{d}$ if and only if it is the gauge $\mathcal{G}_{K}\colon\mathbb{R}^{d}\to\mathbb{R}_{\geq 0}$ of a suitable set $K\subseteq\mathbb{R}^{d}$ , defined by $\mathcal{G}_{K}(z):=\inf\{\lambda\geq 0\mid z\in\lambda K\}$ . E.g., the $2$ -norm is the gauge of the Euclidean unit ball, and the $1$ -norm on $\mathbb{R}^{2}$ is the gauge of the convex polygon that has vertices $(\pm 1,0)^{\mathsf{T}}$ and $(0,\pm 1)^{\mathsf{T}}$ . The precise conditions for $K$ are that it is absorbing, balanced, bounded and convex. Because the gauge of any such set is equal to the gauges of its closure and interior, one may optionally further require that $K$ is closed or open. (See [19, pp. 39–40].) We defer formal definitions to later.

(a) Tilted square (

1

-norm).

(b) Square (

\infty

-norm).

(c) Balanced convex polygon.

Figure 8: Polygons whose gauges are norms, along with evaluation vectors for specific cones.

For now, we only need the linearity property of polygonal norms that allows for the extension. While $\|\cdot\|_{1}$ is linear on each quadrant of the plane, any norm $\mathcal{G}_{K}$ for a suitable polygon $K\subseteq\mathbb{R}^{2}$ is linear on each cone $\Delta_{v,w}:=\{\lambda v+\mu w\mid\lambda,\mu\geq 0\}$ , where $v,w\in\mathbb{R}^{2}$ are two adjacent vertices of $K$ . In fact, we can evaluate $\mathcal{G}_{K}$ on the cone $\Delta_{v,w}$ through the scalar product $\mathcal{G}_{K}(z)=\frac{(w_{2}-v_{2},v_{1}-w_{1})}{v_{1}w_{2}-w_{1}v_{2}}\cdot z$ , which uses a vector that is orthogonal to $v-w$ . See Figure 8 for examples. This property yields piecewise linear CDTW integrands, and it suffices for proving the generalised inductive bound that we desire. If $K$ is a polygon of complexity $k\in\mathbb{N}$ , i.e. it has $k$ vertices and $k$ cones, then the piecewise quadratic functions that had $O(1)$ pieces under $\|\cdot\|_{1}$ have $O(k)$ pieces under $\mathcal{G}_{K}$ .

Lemma 24.

Consider any norm $\mathcal{G}_{K}$ on $\mathbb{R}^{2}$ such that $K$ is a polygon of complexity $k\in\mathbb{N}$ , and let $\mathcal{B}$ be an output border of rank $r>0$ with opposing input border $\mathcal{A}:=\mathcal{B}.\mathrm{opp}$ . Then the number $N_{\mathcal{B}}$ is bounded by $N_{\mathcal{B}}\leq N_{\mathcal{A}}+O(|S^{*}_{\mathcal{A}}|+k)$ with $|S^{*}_{\mathcal{A}}|\in O(r^{2}\cdot k)$ under $\mathcal{G}_{K}$ .

Proof.

As the considered norm $\mathcal{G}_{K}$ is linear on $k$ cones partitioning the plane, fixing an argument of $\mathrm{opt}_{\mathcal{A},\mathcal{B}}$ now yields a piecewise quadratic function with $O(k)$ pieces, which is one of $\rho_{\mathcal{A}}^{\;\!\triangleright},\rho^{\mathcal{B}}_{\;\!\triangleright}$ from Lemma 16 plus the fixed offset resulting from the other. This is again because the $O(1)$ bending points of the optimal paths from Theorem 4 may depend linearly on the non-fixed argument, so that the arguments of $\mathcal{G}_{K}$ in the integrand for the path costs can switch cones $O(k)$ times.

For the same reason, the initialisation of $\mathcal{B}.\mathrm{apx}$ in lines 6–7 of Algorithm 1 and the subroutine call $\mathcal{B}.\hyperref@@ii[alg:propagate-from-adj]{\textsc{% PropagateFromAdjoining}}$ from Algorithm 2 result in $O(k)$ quadratic pieces. Some of these pieces may remain after the call $\mathcal{B}.\hyperref@@ii[alg:propagate-from-opp]{\textsc{% PropagateFromOpposing}}$ , but they cannot result in an increase of complexity: Every dominating best path from $\mathcal{A}$ to a point $\mathcal{B}(t)$ intersects all paths from $\mathcal{B}.\mathrm{adj}$ to points $\mathcal{B}(t^{\prime})$ for $t^{\prime}>t$ . By applying Lemma 11 as in the proof of Proposition 12, it then follows that there are dominating best paths from $\mathcal{A}$ to all such $\mathcal{B}(t^{\prime})$ . Thus, the pieces that the two input borders give are separated, and $\mathcal{B}.\mathrm{adj}$ contributes at most $O(k)$ pieces to $N_{\mathcal{B}}$ . To show $N_{\mathcal{B}}\leq N_{\mathcal{A}}+O(|S^{*}_{\mathcal{A}}|+k)$ , we need to bound the number of pieces given by $\mathcal{A}=\mathcal{B}.\mathrm{opp}$ . For this, we consider the causes that can contribute pieces of $\mathrm{apx}_{\leq s^{*}}$ . Recall that we have

\mathrm{apx}_{\leq s^{*}}(t)=\min_{s\leq s^{*}\land s\leq t}\mathcal{A}.% \mathrm{apx}(s)+\mathrm{opt}_{\mathcal{A},\mathcal{B}}(s,t)=\rho^{\mathcal{B}}% _{\;\!\triangleright}(t)+\min_{s\leq s^{*}\land s\leq t}\mathcal{A}.\mathrm{% apx}(s)+\rho_{\mathcal{A}}^{\;\!\triangleright}(s)

for all $t\in\mathrm{dom}(\mathcal{B})$ due to its definition and Lemma 16, so one possible cause is a switch to another piece of $\rho^{\mathcal{B}}_{\;\!\triangleright}$ . Apart from this, Proposition 17 implies that any new piece of $\mathrm{apx}_{\leq s^{*}}$ may only begin when our assignment of parent points needs to switch to another piece of $\mathcal{A}.\mathrm{apx}$ or to one of $\rho_{\mathcal{A}}^{\;\!\triangleright}$ , or when it needs to switch to or from a parent point among the candidates contained in $S^{*}_{\mathcal{A}}$ . These switches never occur in reverse direction since Lemma 18 says that parent points can be assigned monotonically. Hence, $\rho_{\mathcal{A}}^{\;\!\triangleright}$ and $\rho^{\mathcal{B}}_{\;\!\triangleright}$ contribute $O(k)$ pieces to $N_{\mathcal{B}}$ , while $\mathcal{A}.\mathrm{apx}$ contributes at most $N_{\mathcal{A}}$ pieces. We charge each parent point from $S^{*}_{\mathcal{A}}$ twice to cover the case that it causes a new piece both when switching to it and when switching away from it in a monotone assignment. This contributes at most $2\cdot|S^{*}_{\mathcal{A}}|$ pieces, so we obtain $N_{\mathcal{B}}\leq N_{\mathcal{A}}+O(|S^{*}_{\mathcal{A}}|+k)$ as desired.

We next bound $|S^{*}_{\mathcal{A}}|$ , which is the number of parent candidates for the north-east cell corner. By Definition 15 and Lemma 16, these candidates correspond to the semistrict local minima of the piecewise quadratic function $s\mapsto\mathcal{A}.\mathrm{apx}(s)+\rho_{\mathcal{A}}^{\;\!\triangleright}(s)$ . They can thus only occur at the two domain endpoints, at the breakpoints between pieces, or at points where the derivative is $0$ . More precisely, a local minimum can occur at some breakpoint only if the left piece’s derivative is at most $0$ and the right piece’s derivative it at least $0$ , see Figure 5. This is because the function is additionally continuous, cf. the proof of Lemma 11. Its left and right derivatives are defined everywhere. Let $\partial_{-}$ and $\partial_{+}$ respectively denote the left and right differentiation operator. In the following, we split $\mathrm{dom}(\mathcal{A})$ into open intervals such that $\partial_{-}[\mathcal{A}.\mathrm{apx}(s)+\rho_{\mathcal{A}}^{\;\!% \triangleright}(s)]\geq\partial_{+}[\mathcal{A}.\mathrm{apx}(s)+\rho_{\mathcal% {A}}^{\;\!\triangleright}(s)]$ holds on every interval, which implies that local minima attained within them must have derivative $0$ . For this, we consider the predecessor borders $\mathcal{A}_{0},\dotsc,\mathcal{A}_{r-1}$ of $\mathcal{B}$ , where $\mathcal{A}_{r-1}:=\mathcal{A}$ has rank $r-1$ , and $\mathcal{A}_{i-1}:=\mathcal{A}_{i}.\mathrm{opp}$ has rank $i-1$ for $i\in\{1,\dotsc,r-1\}$ . They all share the same domain.

We introduce partition points for our open intervals at the breakpoints of the functions $\mathcal{A}_{0}.\mathrm{apx}$ and $\rho_{\mathcal{A}}^{\;\!\triangleright}$ as well as, for all $i\in\{1,\dotsc,r-1\}$ , at the breakpoints of $\rho_{\mathcal{A}_{i-1}}^{\;\!\triangleright}$ and $\rho^{\mathcal{A}_{i}}_{\;\!\triangleright}$ from Lemma 16. These are $O(r)$ functions and each has $O(k)$ pieces, so their breakpoints split $\mathrm{dom}(\mathcal{A})$ into $O(r\cdot k)$ open intervals. In addition to proving the above property, we determine the number of semistrict local minima with derivative $0$ to be at most $r$ on each interval, so we get $|S^{*}_{\mathcal{A}}|\in O(r^{2}\cdot k)$ . Let $I\subseteq\mathrm{dom}(\mathcal{A})$ be one of the open intervals. As $\mathcal{A}_{0}.\mathrm{apx}$ has a single piece on $I$ by construction, its left and right derivatives match on all of $I$ . Given $i\in\{1,\dotsc,r-1\}$ , we therefore inductively assume $\partial_{-}\mathcal{A}_{i-1}.\mathrm{apx}(s)\geq\partial_{+}\mathcal{A}_{i-1}% .\mathrm{apx}(s)$ for all $s\in I$ , and show that $\mathcal{A}_{i}.\mathrm{apx}$ also has this property. For $\mathcal{A}_{r-1}=\mathcal{A}$ it then transfers to $s\mapsto\mathcal{A}.\mathrm{apx}(s)+\rho_{\mathcal{A}}^{\;\!\triangleright}(s)$ since $\rho_{\mathcal{A}}^{\;\!\triangleright}$ has a single piece on $I$ . As for the inductive step: Proposition 17 implies that $\mathcal{A}_{i}.\mathrm{apx}|_{I}$ is the lower envelope of

	$\displaystyle\alpha_{i}\colon I\to\mathbb{R}_{\geq 0}\text{,}\quad\text{% defined by}\quad\alpha_{i}(t):=\mathcal{A}_{i-1}.\mathrm{apx}(t)+\rho_{% \mathcal{A}_{i-1}}^{\;\!\triangleright}(t)+\rho^{\mathcal{A}_{i}}_{\;\!% \triangleright}(t)\text{,}$
	$\displaystyle\text{as well as}\quad\alpha_{i,s_{0}}\colon\{t\in I\mid t\geq s_% {0}\}\to\mathbb{R}_{\geq 0}\quad\text{ for all }s_{0}\in S^{*}_{\mathcal{A}_{i% -1}}\text{,}$
	$\displaystyle\text{defined by}\quad\alpha_{i,s_{0}}(t):=\mathcal{A}_{i-1}.% \mathrm{apx}(s_{0})+\rho_{\mathcal{A}_{i-1}}^{\;\!\triangleright}(s_{0})+\rho^% {\mathcal{A}_{i}}_{\;\!\triangleright}(t)\text{.}$

Due to $\rho_{\mathcal{A}_{i-1}}^{\;\!\triangleright}$ and $\rho^{\mathcal{A}_{i}}_{\;\!\triangleright}$ each having a single piece on $I$ by construction, it follows $\partial_{-}\alpha_{i}(t)\geq\partial_{+}\alpha_{i}(t)$ for all $t\in I$ via the induction hypothesis. Meanwhile, for all $s_{0}\in S^{*}_{\mathcal{A}_{i-1}}$ and all $t\in I$ with $t>s_{0}$ we even have $\partial_{-}\alpha_{i,s_{0}}(t)=\partial_{+}\alpha_{i,s_{0}}(t)$ since the argument of $\mathcal{A}_{i-1}.\mathrm{apx}$ in $\alpha_{i,s_{0}}$ is fixed to $s_{0}$ . The lower envelope retains this property: It only switches from one of the functions to another if the next function’s right derivative is less than or equal to the previous one’s. Else, the previous function would still yield smaller values beyond the breakpoint, see Figure 9. Thus, $\partial_{-}\mathcal{A}_{i}.\mathrm{apx}(t)\geq\partial_{+}\mathcal{A}_{i}.% \mathrm{apx}(t)$ holds for all $t\in I$ , including the breakpoints introduced by the lower envelope.

(a) Lower envelope switches functions,
which decreases the right derivative.

(b) Lower envelope does not switch functions,
which keeps equal left and right derivatives.

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\mapsto as^{2}+bs+c$ of the function $\mathcal{A}.\mathrm{apx}$ on $I$ . Such a pair determines the derivative of the pieces to be $s\mapsto 2as+b$ , and thereby fixes the the sole point with derivative $0$ to be $-b/(2a)$ in case of $a\neq 0$ . That means the number of distinct $(a,b)$ -pairs gives an upper bound for the number of parabola vertices. Note that the case of $a=0$ does not contribute additional semistrict local minima, as it yields a derivative of constant value $b$ . Local minima on $I$ have derivative $0$ as argued before, requiring also $b=0$ and thus constant-valued pieces. Any semistrict minimum on those pieces can only be attained at a piece breakpoint. Such a point then has to coincide either with an endpoint of the open interval $I$ , or with a point of derivative $0$ that is fixed by a neighbouring piece’s pair.

We use induction again to prove that $\mathcal{A}_{i}.\mathrm{apx}$ has at most $i+1$ distinct $(a,b)$ -coefficient pairs on $I$ for all $i\in\{0,\dotsc,r-1\}$ . The base case for $i=0$ is true since $\mathcal{A}_{0}.\mathrm{apx}$ has a single piece on $I$ . For $i>0$ we inductively assume that $\mathcal{A}_{i-1}.\mathrm{apx}$ has at most $i$ such pairs, and we consider $\mathcal{A}_{i}.\mathrm{apx}$ in form of the lower envelope from above. Adding $\rho_{\mathcal{A}_{i-1}}^{\;\!\triangleright}$ and $\rho^{\mathcal{A}_{i}}_{\;\!\triangleright}$ , which both have a single piece on $I$ , to $\mathcal{A}_{i-1}.\mathrm{apx}$ preserves the number of $(a,b)$ -pairs. Therefore, $\alpha_{i}$ has at most $i$ pairs on $I$ . Moreover, all functions $\alpha_{i,s_{0}}$ for $s_{0}\in S^{*}_{\mathcal{A}_{i-1}}$ share the single $(a,b)$ -pair of $\rho^{\mathcal{A}_{i}}_{\;\!\triangleright}$ on $I$ because the terms with fixed arguments contribute to $c$ instead of $a$ and $b$ . Together, we have that $\mathcal{A}_{i}.\mathrm{apx}$ has at most $i+1$ distinct $(a,b)$ -coefficient pairs on $I$ . For $\mathcal{A}_{r-1}=\mathcal{A}$ the number $r$ is again preserved by adding the single piece of $\rho_{\mathcal{A}}^{\;\!\triangleright}$ on $I$ , so that we overall have $|S^{*}_{\mathcal{A}}\cap I|\leq r$ as claimed above. $\hfill\blacktriangleleft$

Note that the ideas of counting $(a,b)$ -coefficient pairs [7, Lemma 14] as well as utilising left and right derivatives [7, Lemma 17] originate from the analysis of the exact 1D algorithm. There, the desired properties and bounds were shown separately on subsegments, which were associated with different types of optimal paths as in Figure 1. This required a distinction into a lot of cases, and it caused the analysis to become large and repetitive. One difficulty was the lack of tools for taking a unified approach and exploiting common principles behind function propagations. Lemma 16 now provides such a tool. Although the subsegments are still reflected by the above proof splitting the domain into intervals, our analysis is much shorter and more straightforward than that from [7]. We believe that this constitutes an insightful contribution to the understanding of propagation complexity. A general analysis of unhappy paths in 2D remains open for future work. The costs of these paths cannot be split into two univariate functions (cf. [7, Section 4.5]).

We next use Lemma 24 to establish that under a polygonal norm $\mathcal{G}_{K}$ of complexity $k\in\mathbb{N}$ our algorithm can be implemented with running time $O(n^{4}m\cdot k)$ . This extension is not difficult, yet there are two important aspects for achieving a linear factor in $k$ instead of a worse factor: First, the fact that the procedure for opposing propagation from Proposition 19 uses a single pass on the output border $\mathcal{B}$ , which is an algorithmic contribution of ours. Doing multiple passes as in [7, 5] would lead to a higher running time (cf. [5, Proposition 18]). Second, evaluating $\mathcal{G}_{K}$ at a point $z\in\mathbb{R}^{2}$ requires finding the cone of $K$ that contains $z$ . This is possible in $O(\log(k))$ time via binary search. A naive implementation would do this $O(k)$ times per cell to compute costs of optimal paths, which we avoid by keeping track of how the arguments of $\mathcal{G}_{K}$ switch cones. See the full version for a proof of Theorem 25.

Theorem 25.

Consider any norm $\mathcal{G}_{K}$ on $\mathbb{R}^{2}$ such that $K$ is a polygon of complexity $k\in\mathbb{N}$ . Given polygonal curves $P=\langle p_{0},\dotsc,p_{n}\rangle$ and $Q=\langle q_{0},\dotsc,q_{m}\rangle$ in $(\mathbb{R}^{2},\mathcal{G}_{K})$ , where $n\geq m$ , our $5$ -approximation for CDTW of $P, Q$ under $\mathcal{G}_{K}$ takes $O(n^{4}m\cdot k)$ time.

To approximate CDTW in 2D under the $2$ -norm, we may use a regular polygon inscribed in the Euclidean unit disk. This was done in [5, Corollary 17], and a factor of $1+\varepsilon$ requires polygon complexity $k\in O(\varepsilon^{-1/2})$ . In fact, results from convex geometry imply that we can approximate any fixed norm on $\mathbb{R}^{2}$ by some polygonal norm of the same complexity. More generally, any fixed norm on $\mathbb{R}^{d}$ is $(1+\varepsilon)$ -approximated by some polyhedral norm of complexity $O(\varepsilon^{(1-d)/2})$ . In the following, we outline this polyhedral approximation and its application to our results. Its first ingredient is the geometric characterisation of norms, which we have introduced before: A function is a norm on $\mathbb{R}^{d}$ if and only if it is the gauge $\mathcal{G}_{K}$ of an absorbing, balanced, bounded, convex and closed set $K$ . The first two properties are defined as follows (see [19, p. 11]).

1.

A set $K\subseteq\mathbb{R}^{d}$ is called absorbing (or radial) if for every point $z\in\mathbb{R}^{d}$ there exists some $\lambda_{0}\geq 0$ such that $z\in\lambda K$ holds whenever $|\lambda|\geq\lambda_{0}$ . This ensures that $\mathcal{G}_{K}$ indeed assigns every $z\in\mathbb{R}^{d}$ a real number $\mathcal{G}_{K}(z)=\inf\{\lambda\geq 0\mid z\in\lambda K\}$ . It further implies $\mathbf{0}\in K$ .
2.

A set $K\subseteq\mathbb{R}^{d}$ is called balanced (or circled) in case of $\lambda K\subseteq K$ for all $\lambda\in[-1,1]$ . This yields absolute homogeneity of $\mathcal{G}_{K}$ , i.e. $\mathcal{G}_{K}(\lambda z)=|\lambda|\mathcal{G}_{K}(z)$ for all $z\in\mathbb{R}^{d}$ and all $\lambda\in\mathbb{R}$ . If $K$ is a polyhedron, it further implies that $K$ must have an even number of vertices.

The other three properties are defined as usual, and we do not require those definitions here. Every absorbing, convex and closed set in $\mathbb{R}^{d}$ contains the origin $\mathbf{0}$ in its interior. When a bounded, convex and closed set in $\mathbb{R}^{d}$ has a non-empty interior, it is also called a convex body. Moreover, gauges allow describing any norm $\|\cdot\|$ via its unit sublevel set: We have that $\|\cdot\|$ is the gauge $\mathcal{G}_{M}$ of the balanced convex body $M:=\{z\in\mathbb{R}^{d}\mid\|z\|\leq 1\}$ . (See [19, p. 40].)

The second ingredient is the approximation of convex bodies by (convex) polyhedra, for which there is a vast amount of literature, see [4] for a survey. Note that a $d$ -dimensional polyhedron $K$ generally has different numbers of vertices and facets when $d>2$ , where the facets correspond to the cones on which the gauge $\mathcal{G}_{K}$ is linear. The specific result that we need holds independent of whether one desires a bound on the number of vertices or facets, though this may lead to distinct polyhedra. Because we do not consider the equipped norm to be an input for CDTW, we suppress all constants in the size and dimension of the given convex body by treating it as fixed.

Lemma 26 ([4, Section 4.4]).

Fix any balanced convex body $M\subseteq\mathbb{R}^{d}$ . For every $\varepsilon>0$ there is a convex polyhedron $K\subseteq\mathbb{R}^{d}$ with $O(\varepsilon^{(1-d)/2})$ facets (or vertices) and $M\subseteq K\subseteq(1+\varepsilon)M$ .

For e.g. the sublevel sets of $p$ -norms, which are hyperellipsoids if $1<p<\infty$ , it is not difficult to determine these approximating polyhedra. Constructions for the general case may involve very large constants, see [4, Section 8] for algorithmic considerations. A simple approach, albeit with a higher worst-case asymptotic complexity, is to choose roughly $\varepsilon^{-d}\log(\varepsilon^{-d})$ points uniformly at random from the boundary of $(1+\varepsilon)M$ . Then their convex hull is a $(1+\varepsilon)$ -approximation of $M$ with high probability [18]. Also, note that Proposition 27, which we prove in the full version, might be applicable to other results that work for polyhedral norms, such as the subquadratic DTW algorithm from [12].

Proposition 27.

Fix any norm $\|\cdot\|$ on $\mathbb{R}^{d}$ . For every $\varepsilon>0$ there is another norm $\mathcal{G}_{K}$ on $\mathbb{R}^{d}$ , where $K\subseteq\mathbb{R}^{d}$ is a balanced convex polyhedron with $O(\varepsilon^{(1-d)/2})$ facets (or vertices), such that $\|z\|\leq\mathcal{G}_{K}(z)\leq(1+\varepsilon)\|z\|$ holds for all $z\in\mathbb{R}^{d}$ .

Theorem 28.

Fix any norm $\|\cdot\|$ on $\mathbb{R}^{2}$ , and let $\varepsilon>0$ be arbitrary. Given two polygonal curves $P=\langle p_{0},\dotsc,p_{n}\rangle$ and $Q=\langle q_{0},\dotsc,q_{m}\rangle$ in $(\mathbb{R}^{2},\mbox{$\|\cdot\|$})$ , where $n\geq m$ , we can compute a factor- $(5+\varepsilon)$ approximation for CDTW of $P, Q$ under $\|\cdot\|$ in running time $O(n^{4}m/\varepsilon^{1/2})$ .

Proof.

We use Proposition 27 for $\varepsilon_{0}:=\min\{\frac{\varepsilon}{15},1\}$ to get a norm $\mathcal{G}_{K}$ . By Definition 1, it is

\mathrm{cdtw}_{\|\cdot\|}(P,Q)\leq\mathrm{cdtw}_{\mathcal{G}_{K}}(P,Q)\leq(1+% \varepsilon_{0})^{2}\cdot\mathrm{cdtw}_{\|\cdot\|}(P,Q)\leq(1+\tfrac{% \varepsilon}{5})\cdot\mathrm{cdtw}_{\|\cdot\|}(P,Q)\text{.}

Applying Theorem 25 to $\mathcal{G}_{K}$ thus returns a $(5+\varepsilon)$ -approximation in $O(n^{4}m/\varepsilon^{1/2})$ time. $\hfill\blacktriangleleft$

5 Conclusion

We established the first constant-factor approximation algorithm for CDTW in 2D that has a polynomial running time. It relies on a new integration-based building block and uses a tailored propagation scheme. Another technical contribution of ours is a unified approach to the running time analysis, thanks to novel insights into core principles behind propagation complexity. It is still open whether the additional propagation patterns occurring in exact 2D algorithms, which we circumvented, have polynomial complexity. We also do not know if the approximation factor of $5$ is tight, see ▶ 7 and Section 4.1. To evaluate efficiency and solution quality in practice, an experimental comparison of an exact algorithm and our approximation algorithm would be useful.

Our algorithm works for all polygonal norms. We demonstrated that this allows to approximate CDTW in 2D under any desired norm, making our results applicable in a very broad 2D setting. Recently, there has been an increased interest in solving not only geometric but also combinatorial optimisation problems under more general norm objective functions, see for example [9, 10]. One advantage of measuring the similarity of curves under a norm of choice is the possibility to assign the curve dimensions, which may carry different types of data, suitable weightings [13]. Thus, higher dimensions are a natural direction for future work on CDTW. Known fundamentals do not suffice there since Theorem 4 does not hold in 3D and beyond, see the full version for a counterexample.

References

[1] Sotiris Brakatsoulas, Dieter Pfoser, Randall Salas, and Carola Wenk. On map-matching vehicle tracking data. In Proceedings 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.
[2] Milutin Brankovic. Graphs and Trajectories in Practical Geometric Problems. PhD thesis, University of Sydney, 2022.
[3] Milutin Brankovic, Kevin Buchin, Koen Klaren, André Nusser, Aleksandr Popov, and Sampson Wong. $(k,l)$ -medians clustering of trajectories using Continuous Dynamic Time Warping. In Proceedings of the 28th International Conference on Advances in Geographic Information Systems, pages 99–110. ACM, 2020. doi:10.1145/3397536.3422245.
[4] 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.
[5] Kevin Buchin, Maike Buchin, Jan Erik Swiadek, and Sampson Wong. Fundamentals of computing Continuous Dynamic Time Warping in 2D under different norms. In 20th International Conference and Workshops on Algorithms and Computation, pages 467–482. Springer, 2026. doi:10.1007/978-981-95-7127-7_31.
[6] Kevin Buchin, Maike Buchin, and Yusu Wang. Exact algorithms for partial curve matching via the Fréchet distance. In Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 645–654. SIAM, 2009. doi:10.1137/1.9781611973068.71.
[7] 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.
[8] Maike Buchin. On the Computability of the Fréchet Distance between Triangulated Surfaces. PhD thesis, Freie Universität Berlin, 2007. URL: https://refubium.fu-berlin.de/handle/fub188/1909.
[9] Deeparnab Chakrabarty and Chaitanya Swamy. Approximation algorithms for minimum norm and ordered optimization problems. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 126–137. ACM, 2019. doi:10.1145/3313276.3316322.
[10] Kuowen Chen, Jian Li, Yuval Rabani, and Yiran Zhang. New results on a general class of minimum norm optimization problems. In 52nd 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.
[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.
[12] 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.
[13] Theodor Gutschlag and Sabine Storandt. On the generalized Fréchet distance and its applications. In Proceedings of the 30th International Conference on Advances in Geographic Information Systems, pages 35:1–35:10. ACM, 2022. doi:10.1145/3557915.3560970.
[14] Sariel Har-Peled, Benjamin Raichel, and Eliot W. Robson. The Fréchet distance unleashed: Approximating a dog with a frog. In 41st International Symposium on Computational Geometry, pages 54:1–54:13. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025. doi:10.4230/LIPIcs.SOCG.2025.54.
[15] Koen Klaren. Continuous Dynamic Time Warping for clustering curves. Master’s thesis, Eindhoven University of Technology, 2020. URL: https://research.tue.nl/en/studentTheses/continuous-dynamic-time-warping-for-clustering-curves.
[16] 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.
[17] Mario E. Munich and Pietro Perona. Continuous Dynamic Time Warping for translation-invariant curve alignment with applications to signature verification. In Proceedings of the Seventh IEEE International Conference on Computer Vision, pages 108–115. IEEE, 1999. doi:10.1109/ICCV.1999.791205.
[18] 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.
[19] Helmut H. Schaefer and Manfred P. Wolff. Topological Vector Spaces. Springer, 2nd edition, 1999. doi:10.1007/978-1-4612-1468-7.
[20] Bruno Serra and Marc Berthod. Subpixel contour matching using continuous dynamic programming. In 1994 Proceedings of IEEE Conference on Computer Vision and Pattern Recognition, pages 202–207. IEEE, 1994. doi:10.1109/CVPR.1994.323830.
[21] 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.
[22] 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.
[23] 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.2021.1908927.

[bib.bib1] [1] Sotiris Brakatsoulas, Dieter Pfoser, Randall Salas, and Carola Wenk. On map-matching vehicle tracking data. In Proceedings 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.

[bib.bib2] [2] Milutin Brankovic. Graphs and Trajectories in Practical Geometric Problems. PhD thesis, University of Sydney, 2022.

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

[bib.bib4] [4] 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.

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

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

[bib.bib7] [7] 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.

[bib.bib8] [8] Maike Buchin. On the Computability of the Fréchet Distance between Triangulated Surfaces. PhD thesis, Freie Universität Berlin, 2007. URL: https://refubium.fu-berlin.de/handle/fub188/1909.

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

[bib.bib10] [10] Kuowen Chen, Jian Li, Yuval Rabani, and Yiran Zhang. New results on a general class of minimum norm optimization problems. In 52nd 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.

[bib.bib11] [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.

[bib.bib12] [12] 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.

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

[bib.bib14] [14] Sariel Har-Peled, Benjamin Raichel, and Eliot W. Robson. The Fréchet distance unleashed: Approximating a dog with a frog. In 41st International Symposium on Computational Geometry, pages 54:1–54:13. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025. doi:10.4230/LIPIcs.SOCG.2025.54.

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

[bib.bib16] [16] 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.

[bib.bib17] [17] Mario E. Munich and Pietro Perona. Continuous Dynamic Time Warping for translation-invariant curve alignment with applications to signature verification. In Proceedings of the Seventh IEEE International Conference on Computer Vision, pages 108–115. IEEE, 1999. doi:10.1109/ICCV.1999.791205.

[bib.bib18] [18] 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.

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

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

[bib.bib21] [21] 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.

[bib.bib22] [22] 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.

[bib.bib23] [23] 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.2021.1908927.

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

Abstract

Keywords and phrases:

Category:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

Our Contributions

2 Preliminaries

Definition 1 ([5, Definition 1]).

Definition 2 ([5, Definitions 2 and 12]).

Definition 3 ([5, Definition 3]).

Theorem 4 ([5, Section 2]).

3 Towards a Polynomial Bound

3.1 Building Block

Definition 5.

Lemma 6.

Proof.

▶ Remark 7.

3.2 Algorithm Outline

4 Algorithm Analysis and Specifics

Lemma 8 ([5, Lemma 19]).

Proposition 9.

4.1 Proof of Approximation Factor

Definition 10.

Lemma 11.

Proof.

Proposition 12.

Proof.

Proposition 13.

Proof.

Theorem 14.

4.2 Running Time under the 1-Norm

Definition 15.

Lemma 16 (Happiness Lemma).

Proof.

Proposition 17.

Proof.

Lemma 18.

Proof.

Proposition 19.

Proof.

Definition 20.

Lemma 21.

Proposition 22.

Proof.

Theorem 23.

Proof.

4.3 Extension to Other Norms

Lemma 24.

Proof.

Theorem 25.

Lemma 26 ([4, Section 4.4]).

Proposition 27.

Theorem 28.

Proof.

5 Conclusion

References

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

$\blacktriangleright$ Remark 7.