pith. machine review for the scientific record. sign in

arxiv: 2511.20420 · v2 · submitted 2025-11-25 · 💻 cs.CG

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

Kevin Buchin , Maike Buchin , Jan Erik Swiadek , Sampson Wong This is my paper

Pith reviewed 2026-05-17 04:47 UTC · model grok-4.3

classification 💻 cs.CG
keywords continuous dynamic time warpingCDTWpolygonal curvesEuclidean normcurve similarityFréchet similaritycomputational geometryexact algorithms
0
0 comments X

The pith

Continuous dynamic time warping cannot be computed exactly under the Euclidean 2-norm using only algebraic operations.

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

The paper establishes limits on exact computation for a curve similarity measure that handles outliers and varying sampling rates well. It proves that continuous dynamic time warping under the standard Euclidean distance resists exact solution when restricted to algebraic operations. In place of that, the authors supply an exact algorithm that works when the distance is replaced by a norm close to the Euclidean one. The supporting technical results are shown to extend directly to every norm and to related similarity measures such as partial Fréchet distance. Readers interested in trajectory comparison or shape analysis would value knowing precisely where exact algebraic solutions stop and where reliable approximations begin.

Core claim

We show that CDTW cannot be computed exactly under the Euclidean 2-norm using only algebraic operations, and we give an exact algorithm for CDTW under norms approximating the 2-norm. The latter result relies on technical fundamentals that we establish, and which generalise to any norm and to related measures such as the partial Fréchet similarity.

What carries the argument

Technical fundamentals for exact CDTW computation under norms that approximate the Euclidean 2-norm, enabling both the algorithm and its generalization to arbitrary norms.

If this is right

  • Exact CDTW algorithms become available for every norm once the fundamentals are applied.
  • The same fundamentals yield exact algorithms for partial Fréchet similarity.
  • Designers of curve-similarity tools can avoid the algebraic impossibility by switching to a suitable approximating norm.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • In practice, Euclidean CDTW may require numerical or approximate methods rather than closed-form algebraic solutions.
  • The non-computability result could guide similar investigations for other robust curve distances.
  • Applications in motion analysis or pattern recognition gain concrete guidance on when exact solutions are feasible.

Load-bearing premise

The technical fundamentals established for approximating norms are assumed to generalize without additional restrictions to any norm and to related measures such as partial Fréchet similarity.

What would settle it

An explicit algebraic formula that computes exact CDTW under the Euclidean 2-norm, or a concrete norm or measure for which the established fundamentals fail to produce an exact algorithm.

Figures

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

Figure 1
Figure 1. Figure 1: Simple example of optimal matchings for our CDTW variant Efficiently computing any CDTW variant exactly or with strong approxima￾tion guarantees has turned out to be challenging. The strongest results so far are a pseudo-polynomial-time (1 + ε)-approximation for 2D curves under the Euclidean 2-norm, due to Maheshwari, Sack and Scheffer [23], and a polynomial-time exact algorithm in 1D, first described by K… view at source ↗
Figure 2
Figure 2. Figure 2: Connection between optimal paths through cell terrain and geometric shape of cell terrain, as provided by valleys Theorem 5 ([6, Section 5.5]). Let P , Q be polygonal segments with a valley ℓ of positive slope under a norm ∥ · ∥, and let x, y ∈ R 2 with Ξ := [x1, y1]×[x2, y2] ̸= ∅ be two points in parameter space. If ℓ ∩ Ξ ̸= ∅, then the (x, y)-path tracing line segments from x to xb to yb to y is optimal … view at source ↗
Figure 3
Figure 3. Figure 3: Valley characterisation under a norm with regular hexagons as sublevel sets [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Parameter space whose optimal path candidates switch valleys (b) Now let P := ⟨(4, −2)T,(1, 2)T,(1, −4)T⟩ and Q := ⟨(0, 0)T,(5, 0)T⟩, so that this time ∥P∥2+∥Q∥2 = 11+5 = 16 holds and there are two cells with valleys ℓ1 := {z ∈ R 2 | z1 − z2 = 0} and ℓ2 := {z ∈ R 2 | z1 − z2 = 6} respectively. Optimal path candidates are all γs ∈ Γ∥·∥2 (P, Q) tracing line segments from 0 to (s/2, s/2)T to (s/2 + 6, s/2)T t… view at source ↗
Figure 5
Figure 5. Figure 5: Doubling of adjoining pieces z z [PITH_FULL_IMAGE:figures/full_fig_p012_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: It is opt0,B(t) ≤ cost(γt) for t ∈ dom(B), while (γt)t converges to γ ∗ 0 for t → t0, so Lemma 19 gives limt→t0 opt0,B(t) ≤ limt→t0 cost(γt) = opt0,B(t0). Now consider optimal (0, B(t))-paths γ ∗ t for t ∈ dom(B), and create (0, B(t0))- paths γ t 0 with opt0,B(t0) ≤ cost(γ t 0 ) as above. Hence, opt0,B(t0) ≤ limt→t0 cost(γ t 0 ). By construction, γ t 0 and γ ∗ t share a prefix path up to some point zt. For… view at source ↗
Figure 7
Figure 7. Figure 7: Arrangements on ΣA,B, where each face has a type of optimal paths from bottom/left border A to right border B of a cell for curve segments P , Q under Gψ(R4) Now assume A = opp(B). In particular, it is dom(A) = dom(B) since A, B are parametrised in the same coordinate. We again identify the intersection points of ℓ with A or B and project them into the propagation space ΣA,B by duplicating the pertinent co… view at source ↗
Figure 8
Figure 8. Figure 8: Crossing paths to border B 1 cos(π/k) 0 v z ∗ [PITH_FULL_IMAGE:figures/full_fig_p028_8.png] view at source ↗
read the original abstract

Continuous Dynamic Time Warping (CDTW) measures the similarity of polygonal curves robustly to outliers and to sampling rates, but the design and analysis of CDTW algorithms face multiple challenges. We show that CDTW cannot be computed exactly under the Euclidean 2-norm using only algebraic operations, and we give an exact algorithm for CDTW under norms approximating the 2-norm. The latter result relies on technical fundamentals that we establish, and which generalise to any norm and to related measures such as the partial Fr\'echet similarity.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

1 major / 2 minor

Summary. The paper claims that Continuous Dynamic Time Warping (CDTW) for polygonal curves cannot be computed exactly under the Euclidean 2-norm using only algebraic operations. It presents an exact algorithm for CDTW under norms that approximate the 2-norm, based on newly established technical fundamentals. These fundamentals are asserted to generalize to arbitrary norms and to related measures such as partial Fréchet similarity.

Significance. If the impossibility result and the exact algorithm for approximating norms are correct, the work clarifies fundamental computational limits of CDTW and supplies a practical exact method via norm approximation. The claimed generalization of the technical fundamentals would broaden the results' impact to general norms and measures like partial Fréchet similarity, supporting more robust curve-similarity algorithms in computational geometry that tolerate sampling-rate variation and outliers.

major comments (1)
  1. Abstract and the section establishing the technical fundamentals: the assertion that these fundamentals 'generalise to any norm and to related measures such as the partial Fréchet similarity' is stated without an explicit extension theorem or derivation. If the proofs for approximating norms rely on properties such as strict convexity of the unit ball or differentiability away from axes, the generalization step is load-bearing for the broader utility claim and requires a concrete argument showing the properties transfer without additional restrictions.
minor comments (2)
  1. Clarify the precise definition of 'norms approximating the 2-norm' (e.g., via a specific distance or convergence criterion) at the first point of use.
  2. Add a short discussion or reference to prior work on algebraic computation of Fréchet distance to contextualize the impossibility result for CDTW.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful and constructive review of our manuscript. The feedback on the presentation of the generalization claim is helpful, and we address it directly below.

read point-by-point responses

  1. Referee: Abstract and the section establishing the technical fundamentals: the assertion that these fundamentals 'generalise to any norm and to related measures such as the partial Fréchet similarity' is stated without an explicit extension theorem or derivation. If the proofs for approximating norms rely on properties such as strict convexity of the unit ball or differentiability away from axes, the generalization step is load-bearing for the broader utility claim and requires a concrete argument showing the properties transfer without additional restrictions.

    Authors: We appreciate the referee highlighting the need for greater explicitness on this point. The technical fundamentals are developed from the combinatorial structure of the free-space diagram and the monotonicity properties of admissible warping paths; these rely only on the axioms of a norm (positivity, homogeneity, and the triangle inequality) together with the polygonal nature of the input curves. No appeal is made to strict convexity of the unit ball. Differentiability away from the axes is used solely to guarantee that the critical points arising under the approximating norms remain algebraic; the same structural lemmas carry over to an arbitrary norm by direct substitution of the norm into the distance function, with the algorithm adapting via the same sequence of candidate intervals. The extension to partial Fréchet similarity follows identically by restricting the admissible regions to sub-curves while preserving the same monotonicity and continuity arguments. We will revise the manuscript by inserting a short dedicated subsection (or appendix) that states the extension as a formal corollary and sketches the transfer of each key lemma, thereby making the generalization fully explicit without imposing further restrictions. revision: yes

Circularity Check

0 steps flagged

No circularity: derivation chain is self-contained with new technical fundamentals

full rationale

The paper establishes an impossibility result for exact algebraic CDTW under the Euclidean 2-norm and provides an exact algorithm for approximating norms, relying on technical fundamentals developed within the work. These fundamentals are presented as newly derived and asserted to generalize, without any quoted reduction of outputs to fitted parameters, self-definitions, or load-bearing self-citations that collapse the central claims back to inputs by construction. No equations or sections exhibit patterns such as renaming a fit as a prediction or importing uniqueness via prior author work. The derivation remains independent and self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper relies on standard properties of norms and polygonal curves from computational geometry; no free parameters or invented entities are introduced in the abstract.

axioms (1)
  • standard math Polygonal curves are piecewise-linear and norms satisfy standard metric properties.
    Invoked implicitly when defining CDTW and its computability.

pith-pipeline@v0.9.0 · 5387 in / 1173 out tokens · 31202 ms · 2026-05-17T04:47:50.578729+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

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

    cs.CG 2026-05 unverdicted novelty 8.0

    A 5-approximation algorithm for 2D continuous dynamic time warping under the 1-norm with O(n^5) time, extendable to (5+ε) for any fixed norm.

Reference graph

Works this paper leans on

38 extracted references · 38 canonical work pages · cited by 1 Pith paper

  1. [1]

    Computing the Fréchet distance between two polygonal curves.International Journal of Computational Geometry & Applications, 5(1–2):75–91, 1995.doi:10.1142/S0218195995000064

    Helmut Alt and Michael Godau. Computing the Fréchet distance between two polygonal curves.International Journal of Computational Geometry & Applications, 5(1–2):75–91, 1995.doi:10.1142/S0218195995000064. 14 K. Buchin, M. Buchin, J. E. Swiadek, S. Wong

    work page doi:10.1142/s0218195995000064 1995

  2. [2]

    Thealgebraicdegreeofgeometricoptimizationproblems.Discrete & Computational Geometry, 3(2):177–191, 1988.doi:10.1007/BF02187906

    ChandrajitBajaj. Thealgebraicdegreeofgeometricoptimizationproblems.Discrete & Computational Geometry, 3(2):177–191, 1988.doi:10.1007/BF02187906

    work page doi:10.1007/bf02187906 1988

  3. [3]

    Cambridge University Press, 1990

    Alan Baker.Transcendental Number Theory. Cambridge University Press, 1990. Reissue with updated material.doi:10.1017/CBO9780511565977

    work page doi:10.1017/cbo9780511565977 1990

  4. [4]

    Cambridge Univer- sity Press, 7th edition, 2009

    Stephen Boyd and Lieven Vandenberghe.Convex Optimization. Cambridge Univer- sity Press, 7th edition, 2009. URL:https://web.stanford.edu/~boyd/cvxbook/

    work page 2009

  5. [5]

    On map- matching vehicle tracking data

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

    work page doi:10.5555/1083592.1083691 2005

  6. [6]

    PhD thesis, University of Sydney, 2022

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

    work page 2022

  7. [7]

    InProceedings of the 28th International Conference on Advances in Geographic Information Systems, pages 99–110

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

    work page doi:10.1145/3397536.3422245 2020

  8. [8]

    Four soviets walk the dog: Improved bounds for computing the Fréchet distance.Discrete & Computational Geometry, 58(1):180–216, 2017.doi:10.1007/S00454-017-987 8-7

    Kevin Buchin, Maike Buchin, Wouter Meulemans, and Wolfgang Mulzer. Four soviets walk the dog: Improved bounds for computing the Fréchet distance.Discrete & Computational Geometry, 58(1):180–216, 2017.doi:10.1007/S00454-017-987 8-7

    work page doi:10.1007/s00454-017-987 2017

  9. [9]

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

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

    work page doi:10.1137/1.9781611973068.71 2009

  10. [10]

    Computing Continuous Dynamic Time Warping of time series in polynomial time

    Kevin Buchin, André Nusser, and Sampson Wong. Computing Continuous Dynamic Time Warping of time series in polynomial time. In38th International Symposium on Computational Geometry, pages 22:1–22:16. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022.arXiv:2203.04531,doi:10.4230/LIPICS.SOCG.2022.22

    work page doi:10.4230/lipics.socg.2022.22 2022

  11. [11]

    PhD thesis, Freie Universität Berlin, 2007

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

    work page 2007

  12. [12]

    Bernard Chazelle and David P. Dobkin. Intersection of convex objects in two and three dimensions.Journal of the ACM, 34(1):1–27, 1987.doi:10.1145/7531.24036

    work page doi:10.1145/7531.24036 1987

  13. [13]

    Fréchet distance in subquadratic time

    Siu-Wing Cheng and Haoqiang Huang. Fréchet distance in subquadratic time. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, pages 5100–5113. SIAM, 2025.doi:10.1137/1.9781611978322.173

    work page doi:10.1137/1.9781611978322.173 2025

  14. [14]

    Similarity of polygonal curves in the presence of outliers

    Jean-Lou De Carufel, Amin Gheibi, Anil Maheshwari, Jörg-Rüdiger Sack, and Christian Scheffer. Similarity of polygonal curves in the presence of outliers. Computational Geometry, 47(5):625–641, 2014.doi:10.1016/J.COMGEO.2014.01.0 02

    work page doi:10.1016/j.comgeo.2014.01.0 2014

  15. [15]

    A note on the unsolvability of the weighted region shortest path problem

    Jean-Lou De Carufel, Carsten Grimm, Anil Maheshwari, Megan Owen, and Michiel Smid. A note on the unsolvability of the weighted region shortest path problem. Computational Geometry, 47(7):724–727, 2014.doi:10.1016/J.COMGEO.2014.02.0 04

    work page doi:10.1016/j.comgeo.2014.02.0 2014

  16. [16]

    Curve matching, time warping, and light fields: New algorithms for computing similarity between curves

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

    work page 2007

  17. [17]

    Sur quelques points du calcul fonctionnel.Rendiconti del Circolo Matematico di Palermo, 22(1):1–72, 1906.doi:10.1007/BF03018603

    Maurice Fréchet. Sur quelques points du calcul fonctionnel.Rendiconti del Circolo Matematico di Palermo, 22(1):1–72, 1906.doi:10.1007/BF03018603. Fundamentals of Computing CDTW in 2D under Different Norms 15

    work page doi:10.1007/bf03018603 1906

  18. [18]

    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

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

    work page doi:10.1145/3230734 2018

  19. [19]

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

    work page doi:10.4230/lipics.socg.2025.54 2025

  20. [20]

    Elsevier, 4th edition, 2008

    Alan Jeffrey and Hui-Hui Dai.Handbook of Mathematical Formulas and Integrals. Elsevier, 4th edition, 2008

    work page 2008

  21. [21]

    Continuous Dynamic Time Warping for clustering curves

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

    work page 2020

  22. [22]

    Wilhelmus A. J. Luxemburg. Arzelà’s Dominated Convergence Theorem for the Riemann integral.The American Mathematical Monthly, 78(9):970–979, 1971. doi:10.1080/00029890.1971.11992915

    work page doi:10.1080/00029890.1971.11992915 1971

  23. [23]

    Approximating the integral Fréchet distance.Computational Geometry, 70–71:13–30, 2018

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

    work page doi:10.1016/j.comgeo.2018.01.001 2018

  24. [24]

    Munich and Pietro Perona

    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

    work page doi:10.1109/iccv.1999.791205 1999

  25. [25]

    Lexicographic Fréchet matchings

    Günter Rote. Lexicographic Fréchet matchings. Extended abstract from the 30th European Workshop on Computational Geometry, 2014. URL:https://refubium .fu-berlin.de/handle/fub188/15658

    work page 2014

  26. [26]

    Schaefer and Manfred P

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

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

  27. [27]

    Subpixel contour matching using continuous dynamic programming

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

    work page doi:10.1109/cvpr.1 1994

  28. [28]

    Optimal subpixel matching of contour chains and segments

    Bruno Serra and Marc Berthod. Optimal subpixel matching of contour chains and segments. InProceedings of IEEE International Conference on Computer Vision, pages 402–407. IEEE, 1995.doi:10.1109/ICCV.1995.466911

    work page doi:10.1109/iccv.1995.466911 1995

  29. [29]

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

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

    work page doi:10.1007/s00778-019-00574-9 2020

  30. [30]

    GIScience & Remote Sensing59(1), 200–214 (2022) https: //doi.org/10.1080/15481603.2021.2023840

    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

    work page doi:10.1080/15481603.2021.1908927 2021

  31. [31]

    Vintsyuk

    Taras K. Vintsyuk. Speech discrimination by dynamic programming.Cybernetics and Systems Analysis, 4(1):52–57, 1968.doi:10.1007/BF01074755

    work page doi:10.1007/bf01074755 1968

  32. [32]

    Wildberger and Dean Rubine

    Norman J. Wildberger and Dean Rubine. A hyper-Catalan series solution to polynomial equations, and the Geode.The American Mathematical Monthly, 132(5):383–402, 2025.doi:10.1080/00029890.2025.2460966. 16 K. Buchin, M. Buchin, J. E. Swiadek, S. Wong A Additional Proofs for Section 2 For the sake of completeness, we give proofs of Theorem 5 and Lemma 6. Theo...

    work page doi:10.1080/00029890.2025.2460966 2025

  33. [33]

    Claim (B3).Some algebraic functions α1, α2, β0, β1, β2 : [0, 10] \ {2, 5} →R sat- isfying C′(s) = β0(s) + β1(s) ·ln (α1(s)) + β2(s) ·ln (α2(s))exist

    + 7/2)2 = 99/8 + 7/(2· √ 2)>100/8 = 25/2 = (5/ √ 2)2.⊓ ⊔ So far, we have avoided to evaluate the integrals via antiderivatives, but the third claim relies on this to obtainC′ as a linear combination of logarithms, which allows to apply transcendental number theory by means of Lemma 10. Claim (B3).Some algebraic functions α1, α2, β0, β1, β2 : [0, 10] \ {2,...

    work page

  34. [34]

    = 0is fulfilled on(0 , 10)only by s∗ 0 := 1/929 · 1880· √ 10−3070 + 60· p 16· √ 10 + 61 / 80· √ 10 + 269 ∈(4,4.5). Proof. Let h: R→R be a function withh(s) := √s2 +λ 1s+λ 0 for λ0, λ1 ∈R . By [20, Equation 4.3.4.1.2], the antiderivative oft7→t/h(t)is given by Z t h(t) dt=− λ1 2 ·ln(|2·h(s) + 2s+λ 1|) +h(s) +C. Fundamentals of Computing CDTW in 2D under Di...

    work page

  35. [35]

    Paul Chew and Robert L

    L. Paul Chew and Robert L. (Scot) Drysdale, III. Voronoi diagrams based on convex distance functions. InProceedings of the First Annual Symposium on Computational Geometry, pages 235–244. ACM, 1985.doi:10.1145/323233.323264

    work page doi:10.1145/323233.323264 1985

  36. [36]

    Springer, 3rd edition, 2008

    Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars.Com- putational Geometry: Algorithms and Applications. Springer, 3rd edition, 2008. doi:10.1007/978-3-540-77974-2

    work page doi:10.1007/978-3-540-77974-2 2008

  37. [37]

    Finding the upper envelope ofn line segments in O(nlogn ) time.Information Processing Letters, 33(4):169–174, 1989

    John Hershberger. Finding the upper envelope ofn line segments in O(nlogn ) time.Information Processing Letters, 33(4):169–174, 1989. doi:10.1016/0020-0 190(89)90136-1

    work page doi:10.1016/0020-0 1989

  38. [38]

    Protter and Charles B

    Murray H. Protter and Charles B. Morrey, Jr.Intermediate Calculus. Springer, 2nd edition, 1985.doi:10.1007/978-1-4612-1086-3

    work page doi:10.1007/978-1-4612-1086-3 1985