# Total absolute curvature estimation

Loïc Mazo

► To cite this version:

Loïc Mazo. Total absolute curvature estimation. Acta Applicandae Mathematicae, 2024, 194 (1), pp.5. 10.1007/s10440-024-00694-7. hal-04442863v3

HAL Id: hal-04442863

https://hal.science/hal-04442863v3

Submitted on 28 Sep 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Total absolute curvature estimation

Loïc Mazo

ICube, CNRS - Université de Strasbourg,
Bd S. Brant, Illkirch, 67412, France.

Corresponding author(s). E-mail(s): loic.mazo@laposte.net;

## Abstract

Total (absolute) curvature is defined for any curve in a metric space. Its properties, finiteness, local boundedness, Lipschitz continuity, depending whether there are satisfied or not, permit a classification of curves alternative to the classical regularity classes. In this paper, we are mainly interested in the total curvature estimation. Under the sole assumption of curve simpleness, we prove the convergence, as $\epsilon \to 0$, of the naive turn estimators which are families of polygonal lines whose vertices are at distance at most $\epsilon$ from the curve and whose edges are in $\Omega(\epsilon^\alpha) \cap O(\epsilon^\beta)$ with $0 < \beta \le \alpha < \frac{1}{2}$. Besides, we give lower bounds of the speed of convergence under an additional assumption that can be summarized as being "convex-or-Lipschitz".

**Keywords:** total curvature, geometric feature estimate, digital geometry

## 1 Introduction

Total curvature is the arithmetic sum of absolute direction changes along a parametrized curve. As such, it is an indicator of the complexity of the curve [1, 2]. For this reason, it is used as a regularization term in segmentation processes [3–6] or as a characterization of digital straightness [7]. Moreover, due to Fenchel’s Theorem which states that any closed curve has a total curvature greater than $2\pi$ if not convex and equal to $2\pi$ if convex ([8] for the regular case and [9] for the general case), it is also a characterization of convexity [7]. Besides, locally limiting total curvature makes it possible to isotopically link the curve and its digitization [10]. Let us add that, contrary to the differential curvature, total curvature can be defined for any curve, that is without smoothness assumption. As reported in [11], this advantage was already underlined by J. Steiner at the end of the nineteenth century about the
total mean curvature of surfaces. Another interesting property when estimating the total curvature from a digital image is its scale invariance (it is dimensionless). Thus, total curvature estimation does not require knowledge of the image resolution. To our knowledge, although there is an important literature on estimating the differential curvature (see for instance the introductory sections in [12–14]) there is no reference on curve total curvature estimation, a fortiori from imprecise data (see the introduc- tory section in [11] for surface total mean curvature estimation). Thereby, this paper constitutes a first attempt on giving upper bounds on the convergence orders of a total curvature estimator for a variety of curves.

The definition of total curvature used in our paper is that suggested by R. H. Fox to Milnor [15] and extensively developed by Alexandrov and Reshetnyak [9] (see also the shorter paper [16]). Let $E^n$ be an $n$-dimensional Euclidean space. The total curvature $\kappa(P)$ of a polygonal line $P$ in $E^n$ is the sum of its exterior angles (see Figure 1) and the total curvature of a parametrized curve $\gamma$ in $E^n$ is the supremum of the total curvatures of its inscribed polygonal lines:

$$ \kappa(\gamma) = \sup\{\kappa(P) \mid P \text{ inscribed in } \gamma\}. \qquad (1) $$

Clearly, it doesn’t matter how fast the curve is traveled due to the parametrization. In Section 2 we will specify the notion of curve used later in the article and what is meant by “inscribed polygonal line”.

<figure><img src="image_2.png" /><figcaption>**Fig. 1:** Left: the curve and its inscribed polygonal line are traversed from left to right. Right: the curve and the polygonal line are traversed from right to left. The total curvature of the polygonal line is the sum of its absolute “turns” at each of its interior vertices. These turns are marked in green on the left and in red on the right. Their values are independent of the curve orientation. The total curvature of the curve is the supremum of the total curvatures of its inscribed polygonal lines.</figcaption></figure>

Following Alexandrov, we call *turn* the total curvature when referring to Formula (1). The turn generalizes the total curvature of differential geometry: for curves of class $C^2$, both definitions coincide. The total curvature may also be defined by
<figure><img src="image_3.png" /><figcaption>**Fig. 2:** The red polygonal line $Q$ is called an $\epsilon$-approximation of the black curve $C$ if its vertices are at distance at most $\epsilon$ from the vertices of some inscribed polygonal line $P$ (in blue) whose ends coincide with the ends of $C$. The turn of $Q$ is an estimate of the turn $\kappa(C)$ of the black curve. The difference between $\kappa(C)$ and the turn $\kappa(P)$ of the blue polygonal line is called the *discretization error*, and the difference between $\kappa(P)$ and $\kappa(Q)$ is called the *quantization error*. In this paper, we investigate whether such an estimator $\kappa(Q)$ converges toward $\kappa(C)$, and with what speed, as both $\epsilon$ and the edge lengths of $Q$ tend towards 0.</figcaption></figure>

means of circumscribing polygons as done in [17] for finite unions<fnref n="1" /> of convex arcs<fnref n="2" />. Nevertheless, the definition is less general than that of Milnor.

In this paper, we aim to investigate whether the definition of the turn given by Formula (1) yields an easy but convergent way of estimating the total curvature, especially in the case of imprecise data like digitized sample data. Specifically, do sequences of polygonal lines with increasingly shorter edges and vertices closer and closer to the curve yield a convergent sequence of estimates (see Figure 2)? Notice that, without additional hypotheses, the answer to this question is “no”. Just consider that the scanning of a ramp can yield a staircase.

In the sequel, we will refer to those estimates by means of polygonal lines as total curvature *naive estimators*. Of course, total curvature may be computed from differential curvature estimates. But proceeding in this way involves restricting us to $C^2$ class curves. In view of the simplicity of the total curvature definition compared to the curvature one, directly estimating total curvature seems preferable. On the contrary, a total curvature estimate could serve as a basis for the differential curvature estimate. Indeed, in the same calculation loop one can compute the turn and the length of a polygonal line interpolating a small piece of curve. The quotient of these two values provides an estimate of the average differential curvature on the curve arc which could be used as an estimate of the differential curvature at some point of the arc. This is not so far from what is done by the integral based curvature estimator [18] which assumes a constant curvature inside a ball of given radius. As for how to deal with data imprecision, error bounds on differential curvature estimates have been obtained directly by fitting digital circular arcs with quantified data [19–21]. Another

<footnote n="1">¹More precisely, the authors define the total curvature of convex curves then derive the total signed curvature of curves that are finite unions of convex arcs</footnote>

<footnote n="2">²A convex arc is a simple curve whose support is a connected bounded subset of the boundary of a plane convex set (see Section 3.2.1).</footnote>
way to obtain a bound on the error of the estimate is to decompose it into two terms, the first one due to discretization and the second one due to quantization (or data imprecision). This is the strategy followed, for instance, in [14, 18] for differential curvature estimation based on integral invariants. With regard to the estimation of the total curvature, without any assumptions on the shape of the curve, we need to proceed by decomposition.

Given exact sample points, thanks to a lemma from [9], we prove in Section 3.1 the convergence of the naive estimators for simple curves. But this result is purely qualitative and says nothing about the convergence speed. In the general case, the estimation of the total curvature can be tricky because sample points may be collinear in the worst case. This is also the case with the differential curvature and lead generally to exclude the possibility of such collinear configurations. For instance, the integral invariant based curvature estimator [14, 22, 23] relies on lemmas shown in [24]. And the first of these lemmas [24, Lemma 1] excludes a limit case of the collinear configuration 3 In the case of total curvature, excluding collinearity that is considering convex shapes, greatly simplifies the estimation. Indeed, it is easily derived from Fenchel's theorem that the total curvature of a convex curve only depends on the angle between the tangent directions at its ends (Lemma 6). This property was also noticed by Latecki and Rosenfeld in [17] for their definition of total curvature using circumscribing polygons. Observe that the existence of those tangent directions is ensured by convexity. Nevertheless, bounding the tangent estimation error requires extra regularity. Since we are interested in measuring the total curvature and we mainly control the Euclidean distance between the sample points, the regularity property used here is the turn Lipschitz continuity with respect to the Euclidean distance. More specifically, given a simple curve $\gamma$ in $E^n$ whose image is denoted by $|\gamma|$, we say that its turn is k-strongly Lipschitz if

$$ \forall x, y \in |\gamma|, \kappa(\gamma_x^y) \le k\|x - y\|, \quad (2) $$

where $\gamma_x^y$ denotes the curve arc 4 between the points $x \in |\gamma|$ and $y \in |\gamma|$. Actually, the class of curves with strongly Lipschitz turn is well-known by its other characteristic properties, see Table 1 and Figure 3. In particular, in Appendix A and Appendix B, we give the proof that a simple parametrized curve has a strongly Lipschitz turn if and only if its turn is both locally bounded and Lipschitz with respect to the geodesic distance and if and only if the arc length parametrization of the curve is of class $C^{1,1}$ and regular. In Section 5, the strong Lipschitz continuity assumption is invoked to obtain speeds of convergence of the naive turn estimators.

In the general case, that is with non convex curves, the collinear configuration produces maximum estimation errors. Indeed, by definition of the turn, the error caused by the naive estimator is at most equal to the curve total curvature. Equality happens when the turn of the polygonal interpolation is null. For instance, a sine curve may be interpolated by a straight segment. Nevertheless, when studying the convergence of a curvature estimator as curve sampling densifies, resampling with more and more points should reduce the proportion of the collinear configuration occurrences and tend to make it vanishing. This is true when the curve is composed of

<footnote n="3">3 In this case, the curve is cut by one of its tangents.</footnote>

<footnote n="4">4 For a closed curve, we take the curve arc that has the smaller curvature.</footnote>
<table><caption>**Table 1:** Overview of some characteristic properties of curves with strongly Lipschitz turn. For precise definitions and complete statements of equivalences, the reader is invited to consult the references.</caption><thead><tr><th></th><th>Property</th><th>Description</th><th>Equivalence</th></tr></thead><tbody><tr><td>(A)</td><td>Strongly Lipschitz turn</td><td>A simple curve has a <i>strongly Lipschitz turn</i> if its turn is Lipschitz with respect to the Euclidean distance.</td><td></td></tr><tr><td>(B)</td><td>C<sup>1,1</sup></td><td>A curve &gamma; is C<sup>1,1</sup> if it is C<sup>1</sup> and its derivative &gamma;' is Lipschitz.</td><td>(B) &harr; (A)<br>Appendix B</td></tr><tr><td>(C)</td><td>Positive reach [25]</td><td>The <i>medial axis</i> MA of <i>C</i> is the sets of space points that have at least two nearest points on <i>C</i>. The <i>reach</i> is the infimum distance between the points of <i>C</i> and MA.</td><td>(B) &harr; “&gamma;, as set, has a positive reach” [25]</td></tr><tr><td>(D)</td><td>Par(r)-regularity [26–29]</td><td>Basically, a plane curve is <i>par(r)-regular</i> if a ball with radius <i>r</i> can roll smoothly on both sides of the curve</td><td>(D) &harr; (C)<br>[30]</td></tr><tr><td>(E)</td><td>Locally bounded turn [31]<br>Lipschitz turn [31]</td><td>A curve has a <i>&delta;-locally bounded turn</i> if its turn between any two points at Euclidean distance less than &delta; is at most &pi;/2.<br>A curve has a <i>Lipschitz turn</i> if its turn is Lipschitz with respect to the geodesic distance.</td><td>(E) &harr; (D)<br>[32]<br>(E) &harr; (A)<br>Appendix A</td></tr></tbody></table>

<figure><img src="image_4.png" /><figcaption>**Fig. 3:** Representation of the properties described in Table 1. Apart from the length of the straight segment *AB*, the left and right black curves are identical. Their medial axes are depicted in red. On each picture, the gray balls have radii strictly smaller than the reach of the curve. Then, they can roll along the curve. The green segments indicate the maximum values of *δ*, the turn local boundedness parameter and the blue, dotted segments indicate the smallest radii of curvature of the curves, which are related to the Lipschitz parameters.</figcaption></figure>

a finite number of pair of convex arcs with opposite convexities, that is when there is finitely many inflection points. It can be extended to curves with finitely many limit points of inflection points (see Section 5.2.4) but is not true in the general case (see Figure 7 which describes a nowhere convex curve with finite turn). Rather than “ruling out pathological arcs which have infinitely many inflections or which turn infinitely often” [17], here we just exclude curves that are difficult to travel, that is non simple curves (see Section 3.1). We prove the correctness of the turn limit for simple curve
polygonal interpolations when edge lengths vanish. In the case of simple curves with finite turns, we propose to measure the non convex parts relative to a resolution and derive a bound on the turn estimation error. In Section 5.2, we deal with finite and infinite concatenations of convex curves.

The turn estimation error due to data imprecision is more easy to handle than the one due to the discretization. In this paper (Section 4), we bound the former geometrically. Our proof is not optimal but very simple. We decompose the error due to data imprecision in a sum of elementary errors caused by each triplet of consecutive sample points.

Taking into account both errors, the one due to the discretization of the curve and the one due to the uncertainty on the data, the global error depends on hypotheses related to convexity and turn continuity. Let $\mathcal{C}$ be a simple curve in $E^n$ and $(Q_\epsilon)_{\epsilon>0}$ be a family of $\epsilon$-approximations of $\mathcal{C}$.

* In the general case, if the edge lengths of $Q_\epsilon$ tend towards 0 as $\epsilon \to 0$ while dominating $\epsilon^{1/2}$, then $\kappa(Q_\epsilon)$ tends towards $\kappa(\mathcal{C})$ as $\epsilon \to 0$ (Proposition 15).

* The case of a convex plane curve is very special. It is in our interest to take into account only the first and last edges of the polygonal lines $Q_\epsilon$. If the lengths of these edges are bounded from above by $\epsilon^\beta$ and dominate $\epsilon^\alpha$ where $0 < \beta \le \alpha < 1$, then

$$ \kappa(\mathcal{C}) - \kappa(Q'_\epsilon) = O(\epsilon^\beta) + O(\epsilon^{1-\alpha}), $$

where $Q'_\epsilon$ is derived from $Q_\epsilon$ by linking the first and last edges of $Q_\epsilon$ by a single edge (Proposition 17). In particular, the best convergence speed is obtained taking $\alpha = \beta = \frac{1}{2}$.

* Let us now assume that $\mathcal{C}$ is convex by parts and that its turn is strongly Lipschitz, at least in the neighborhoods of the gluing points (Proposition 18). If the edge lengths of $Q_\epsilon$ are bounded from above by $\epsilon^\beta$ and bounded from below by $\epsilon^\alpha$ where $0 < \beta \le \alpha < 1/2$, then

$$ \kappa(\mathcal{C}) - \kappa(Q'_\epsilon) = O(\epsilon^\beta) + O(\epsilon^{1-2\alpha}). $$

The best asymptotic error bound —equal to $\epsilon^{1/3}$— is obtained taking $\alpha = \beta = \frac{1}{3}$. Shortest edges increase the error due to the imprecision of the data whereas longest edges increase the error due to the discretization. This error is comparable to differential curvature estimation error found in [14, 21].

* For curves with infinitely many convex arcs, we study an example with an inflection limit point: $x \mapsto x^\eta \sin(\pi/x)$ where $\eta \ge 4$ (Section 5.2.4). In this case, if the edge lengths of $Q_\epsilon$ are bounded from above by $\epsilon^\beta$ and bounded from below by $\epsilon^\alpha$ where $0 < \beta \le \alpha < 1/2$, then

$$ \kappa(\mathcal{C}) - \kappa(Q'_\epsilon) = O(\epsilon^{\beta/2}) + O(\epsilon^{1-2\alpha}). $$

The best convergence speed is $\epsilon^{1/5}$ taking $\alpha = \beta = \frac{2}{5}$.

In Section 6, in order to give an insight on the constants hidden by the asymptotic notations, we present the results of a small set of tests using naive turn estimators on
three plane curves. Section 7 concludes the paper and presents some further researches and developments in link with the article.

# 2 Background

We begin by recalling a few definitions and some known results about curves and their turns.

## 2.1 Curves

The turn is a geometric feature of a curve, that is, it does not depend on the parametrization. However, it is not just a set of space points. The direction of travel is important. So, let us give some definitions to specify the sort of curves that will be considered hereafter.

A parametrized curve in $E^n$ is a continuous map $\gamma: I \to E^n$ where $I$ is a compact interval of $\mathbb{R}$. The image $\gamma(I)$ is called the *support* of the curve and denoted by $|\gamma|$. A *change of parameter* for $\gamma$ is an homeomorphism $\phi: J \to I$ where $J$ is a compact interval of $\mathbb{R}$ and the parametrized curve $\gamma' = \gamma \circ \phi$ is called a *reparametrization* of $\gamma$. A *curve* is a parametrized curve up to parameter changes: $\gamma_1: I \to E^n$ and $\gamma_2: J \to E^n$ define the same curve if there exists a parameter change such that $\gamma_2 = \gamma_1 \circ \phi$. An *oriented curve* is a parametrized curve up to increasing parameter changes. Parametrized curves defining the same curve $C$ have the same support (the converse is false). This support is denoted by $|C|$.

A parametrized curve $\gamma$ is *normal* if, for any $x \in |\gamma|$, the connected component of $\gamma^{-1}(x)$ are singletons. In this case, any reparametrization of $\gamma$ is normal. If the support of a curve is a singleton, we say that the curve is *degenerated*. A curve $C$ is *simple* if it admits a one-to-one parametrization. In this case, any parametrization of $C$ is one-to-one. Given a curve $C$, a parametrization $\gamma$ of $C$ is *regular* if $\gamma$ is differentiable and its derivative nowhere vanish.

Actually, the above definition of a curve is a bit too restrictive. It allows to change the travel speed, but not to stop on the way. That is why in [9], the equivalence used to define a curve is coarser. Changes of parameter are only requested to be monotonic in a broad sense, that is non-increasing or non-decreasing. The drawback is that the symmetry property of the equivalence relation requires to define inverse to non-increasing (or non-decreasing) functions. Obviously, this complicates the equivalence definition. Anyway, both definitions of curves coincide for normal curves and any non-degenerate curve has a normal parametrization [9, 1.2.1]. In this article, which aim at evaluating a turn estimator, we choose to use the simple, and well-known, definition of curves with one-to-one parameter changes. Furthermore, to simplify the presentation of the results, we will only consider normal oriented curves and we do not treat the particular case of closed curves.

Let us now describe the polygonal lines used to estimate the turn of a curve.
<figure><img src="image_5.png" /><figcaption>**Fig. 4:** The Peano curve whose ends are *a* and *b* fills the square of which [*a*, *b*] is a diagonal. If the curve is oriented from *a* to *b*, using the parametrization given by G. Peano in [33], the interior of the small red square is filled before the interior of the small blue square. Now, consider a linear interpolation *P* of this Peano curve whose support is included in the segment [*a*, *b*]. If *P* has vertices inside the red square and inside the blue square, *P* cannot be simple.</figcaption></figure>

## 2.2 Linear interpolations

Most of the vocabulary presented here is borrowed from [9]. Given a curve $\mathcal{C}$ in $E^n$, a chain $\xi$ is an ordered sequence of points on that curve. A polygonal line $P = [x_i]_{i=0}^m$ is inscribed into the curve $\mathcal{C}$ if on the latter there can be found a chain $\xi = \langle y_i \rangle_{i=0}^m$ such that for any $i$, $y_i$ coincides with $x_i$ as a space point. Finally, an inscribed polygonal line $P$ is a linear interpolation of $\mathcal{C}$ if its endpoints are the endpoints of $\mathcal{C}$. If the curve $\mathcal{C}$ is not simple, it may happen that several chains spatially coincide with a linear interpolation. For instance, consider a straight segment [*a*, *b*] which is traveled three times, from *a* to *b*, then from *b* to *a* and again from *a* to *b*. Divide this segment by means of *m* equally spaced inner points. We get a simple linear interpolation $P_m$ of the curve. The reader can check that there exist $2m+3$ chains of that curve that share with $P_m$ the same sequence of ordered space points. If, instead of traveling three times the segment [*a*, *b*], we go from point *a* to point *b* following the Peano curve [33], thus filling a square of which [*a*, *b*] is a diagonal, the polygonal line $P_m$ is no more inscribed in the curve but for a few small values of *m* (see Figure 4).

We will now focus on sequences of linear interpolations with vanishing edge lengths.

## 2.3 Frechet convergence and turn limit

Before examining the question of the convergence of linear interpolations sequences towards the interpolated curve, let us give some vocabulary, mostly again from [9]. Recall that in a metric space, the diameter of a set is the supremum of the distances between two points of the set. Then, given a curve $\mathcal{C}$ in $E^n$ and a chain $\xi$, the biggest of the diameters of the arcs into which $\mathcal{C}$ is divided by the vertices of $\xi$ is called the *module* of the chain and is denoted through $\lambda(\xi)$. Let $P$ be a linear interpolation of $\mathcal{C}$. The supremum of the modules of the chains that spatially coincide with $P$ is called
the module of P relative C and is designated through $\lambda_C(P)$. Notice that, contrary to [9], we will omit the index C in the following if and only if $P = C$. Hence, $\lambda(P)$ denotes the length of the largest edge of P.

The Fréchet distance between two curves C and C' in $E^n$ is defined by

$$ \rho(C, C') = \inf_{\gamma, \gamma' \in [0,1]} \sup_{t \in [0,1]} \|\gamma(t) - \gamma'(t)\|, $$

where $\gamma$ and $\gamma'$ are any parametrization of C and C' defined on $[0, 1]$. The set of curves in $E^n$ equipped with the Fréchet distance is a complete metric space [9, Theorem 1.4.2]. A sequence of curves $(C_m)_{m \in \mathbb{N}}$ converges to the curve C if $\rho(C_m, C)$ tends towards 0 as $m \to 0$ or, equivalently if there are parametrizations $\gamma$ of C and $\gamma_m$ of $C_m$ ($m \in \mathbb{N}$), defined on $[0, 1]$ such that the functions $\gamma_m$ uniformly converge towards $\gamma$ [9, Lemma 1.4.1].

Let us now recall three results of Alexandrov and Reshetnyak on the Frechet convergence, the inscribed polygonal lines and the turn limit. The first one gives a sufficient condition for a sequence of curves to converge towards a given curve.

**Lemma 1** ([9], page 23). Let C be a curve in the metric space $(M, \chi)$ and $(C_m)$, $m = 1, 2, \dots$ be a sequence of curves in $M$. Let us assume that for any $\epsilon > 0$ there is a positive integer $m_\epsilon$, such that at $m \ge m_\epsilon$ one can construct on the curves C and $C_m$ the sequences of points $x_1, x_2, \dots, x_k$ on the curve C and $x'_1, x'_2, \dots, x'_k$ on the curve $C_m$, such that $\chi(x_i, x'_i) < \epsilon$ for all i and the diameters of the arcs into which the curves C and $C_m$ are divided by the points are less than $\epsilon$. In this case, the curves $C_m$ converge to the curve C as $m \to \infty$ [for the Fréchet distance].

In [9], the following corollary is immediately deduced from Lemma 1

**Corollary 2** ([9], page 23). Let C be a curve in an n-dimensional Euclidean space, and let $P_m$, $m = 1, 2, \dots$, be an arbitrary sequence of polygonal lines inscribed in it. In this case, if at $m \to \infty$ $\lambda_C(P_m) \to 0$, then the polygonal lines $P_m$ converge to the curve C.

The third result makes the link with the turn.

**Theorem 3** ([9], page 121). Let C be a curve in an n-dimensional Euclidean space, and let $P_m$, $m = 1, 2, \dots$, be an arbitrary sequence of polygonal lines inscribed into it converging to the curve C at $m \to \infty$. Then $\kappa(C) = \lim_{m \to \infty} \kappa(P_m)$.

In Section 3.1, we will replace Corollary 2 by a new result using the modules $\lambda(P_m)$ instead of the modules $\lambda_C(P_m)$, which are unknown, at the cost of a curve simpleness assumption.

## 3 Discretization error

In order to estimate the turn of a shape boundary arc, we use a polygonal line built from the shape digitization. The difference between the true turn of the arc and the polygonal line turn is split into two terms, the discretization error and the quantization error. The discretization error is the difference between the turn of the curve and the turn of a polygonal line built from a sequence of sample points. These points lie on the curve unlike those coming from the digitization process which lie close to the curve.
## 3.1 Simple curves

When estimating the turn of a curve $C$ in $E^n$ by means of a polygonal line $P$, we have control over the module $\lambda_P(P)$, that is over the edge lengths of $P$, not over $\lambda_C(P)$. Hence, Corollary 2 is not useful to find converging sequences of polygonal lines. Now, the question is: can we replace the module $\lambda_C(P)$ by the module $\lambda_P(P)$ in the corollary to Lemma 1? Unfortunately, the answer is negative in the general case. Indeed, consider the segment $[a, b]$, which is traveled three times, and the sequence of linear uniform interpolations $(P_m)_{m=0}^\infty$ described in Section 2.2. Then, the edge length of $P_m$, which is $\|b - a\|/(m + 1)$, tends towards 0 as $m \to \infty$ but the Fréchet distance between the curve and $P_m$ does not vanish, staying equal to $\|b - a\|/2$. In the case of the Peano curve, also described in Section 2.2, we saw that $(P_m)_{m=0}^\infty$ is not a valid sequence of linear interpolations. But, it can be seen from the formula given by G. Peano in order to compute the parameters associated to a given point that any polygonal line from $a$ to $b$ that follow the edges of the square filled by the Peano curve is actually a linear interpolation of the curve. Nevertheless, obviously no sequence of such polygonal lines does converge towards the Peano curve. In both previous examples, the reason convergence does not occur is that the considered linear interpolations may avoid significant parts of the curve. This is due to the fact that the curve is not simple. And indeed, as stated by the following proposition, it is enough to add the simpleness hypothesis to obtain the convergence of a sequence of linear interpolations whose edge lengths tends to 0.

**Proposition 4.** Let $C$ be a simple curve in an $n$-dimensional Euclidean space, and let $P_m$, $m = 1, 2, \dots$, be a sequence of linear interpolations of $C$. In this case, if at $m \to \infty$, $\lambda(P_m) \to 0$, then the polygonal lines $P_m$ converge to the curve $C$.

*Proof.* Let $C$ be a curve in an $n$-dimensional Euclidean space and let $P_m$, $m = 1, 2, \dots$, be a sequence of polygonal lines inscribed in $C$ with $\lambda(P_m) \to 0$ as $m \to \infty$. Let us consider a normal parametrization of $C$, $\gamma: [0, 1] \to |C|$. The map $\gamma$ is an homeomorphism for $C$ is simple. Since the domain of $\gamma$ is compact, $|C|$ is compact. Then, $\gamma$ and $\gamma^{-1}$ are uniformly continuous. Let $\mu_m$ be the norm of the partition of $[0, 1]$ formed by $P_m$'s vertex parameters. Since $\gamma^{-1}$ is uniformly continuous,

$$ \lim_{m \to \infty} \lambda(P_m) = 0 \implies \lim_{m \to \infty} \mu_m = 0, $$

and, since $\gamma$ is uniformly continuous,

$$ \lim_{m \to \infty} \mu_m = 0 \implies \lim_{m \to \infty} \lambda_C(P_m) = 0. $$

Hence, $\lim_{m \to \infty} \lambda_C(P_m) = 0$. We conclude the proof by invoking Corollary 2: the polygonal lines $P_m$ converge to the curve $C$. $\square$

From the previous proposition and Theorem 3, we immediately derive the following result.

**Corollary 5.** Let $C$ be a simple curve in an $n$-dimensional Euclidean space and let $(P_m)_{m=0}^\infty$ be a sequence of linear interpolations of $C$. If $\lambda(P_m) \to 0$ as $m \to \infty$, then, $\lim_{m \to \infty} \kappa(P_m) = \kappa(C)$.
Now that we have proved the convergence of the turns of linear interpolations with vanishing edges, let us look at the discretization error. In the case where the curve has infinite turn, the error is infinite. Indeed, the turn of any polygonal line with finitely many vertices is finite. It is upper bounded by $(m - 2)\pi$ where $m$ is the number of vertices. We will from now focus on the case of curves with finite turns.

## 3.2 Simple curves with finite turn

Given a curve $C$ in $E^n$ and a linear interpolation $P$, the definition of the turn implies that $0 \le \kappa(P) \le \kappa(C)$. Therefore,

$$0 \le \kappa(C) - \kappa(P) \le \kappa(C). \qquad (3)$$

The lower bound 0 of the discretization error is reached for instance when $C$ is a polygonal line and $P = C$. The upper bound, $\kappa(C)$, is reached for instance if $P$ is just a straight segment joining the ends of $C$ but also if $C$ is the sine curve $y = \sin(x)$ where $x \in [0, k\pi]$ ($k$ being any positive integer) and the vertices of $P$ are the points of the $x$ axis with abscissa $i\pi$ for $0 \le i \le k$. On a 2D convex curve, the upper bound in (3) can be improved. This is the purpose of the following section.

### 3.2.1 Discretization error on a 2D convex curve

By convex curve, we refer to a simple curve whose support is a connected bounded subset of the boundary of a plane convex set. Observe that an arc of spiral may have everywhere a positive (or negative) differential curvature without being a convex curve in the above sense.

First, we note that, due to Fenchel's Theorem, a convex curve has a finite turn, equal to at most $2\pi$. Moreover, it is well known that a convex curve has left and right tangent everywhere (see for instance [34]). Actually, this is also the case for any curve of finite turn [9, Theorem 5.1.2]. Our first statement regarding convex curves, showcased by Figure 5, expresses that the turn of a plane convex arc only depends on the tangent lines at its ends.

**Lemma 6.** Let $C$ be a curve of finite turn from the point $a$ to the point $b$, $a \ne b$, in $E^n$. Let $t_a$ and $t_b$ be respectively the right unit tangent vector at $a$ and the left unit tangent vector at $b$. Then,

$$\kappa(C) \ge \angle(t_a, \vec{ab}) + \angle(t_b, \vec{ab}).$$

Moreover, the equality occurs if and only if $C$ is a plane convex curve.

*Proof.* The lemma is a direct consequence of two theorems proved in [9]:

(a) (Th. 5.1.5) The turn of a closed curve is at least $2\pi$. The equality is valid only for convex curves.

Thus, with the hypotheses of the lemma

$$\kappa(C \cup [a, b]) \ge 2\pi,$$
and the equality occurs if and only if $\mathcal{C}$ is convex.

(b) (Th. 5.1.3) Let $X$ be a curve with finite turn and $x$ a point on $X$ which is not an extremity of $X$. Let $\mathbf{t}_1$ and $\mathbf{t}_r$ be the left and right unit tangent vectors to $X$ at $x$. Then,

* if $X$ is a closed curve, $\kappa(X) = \kappa(X \setminus \{x\}) + \angle(\mathbf{t}_1, \mathbf{t}_r)$;

* otherwise, $\kappa(X) = \kappa(X_l) + \kappa(X_r) + \angle(\mathbf{t}_1, \mathbf{t}_r)$ where $X_l$ and $X_r$ are the left and right part of $X \setminus \{x\}$.

Thus, $\kappa(\mathcal{C} \cup [a, b]) = \kappa(\mathcal{C}) + \angle(\mathbf{t}_b, \vec{ba}) + \angle(\vec{ba}, \mathbf{t}_a)$. That is,

$$ \kappa(\mathcal{C} \cup [a, b]) = \kappa(\mathcal{C}) + 2\pi - \angle(\mathbf{t}_b, \vec{ab}) - \angle(\vec{ab}, \mathbf{t}_a). $$

Putting together Items (a) and (b) straightforwardly ends the proof. $\square$

<figure><img src="image_6.png" /><figcaption>**Fig. 5:** Lemma 6 states that the turn of the blue convex curve $\mathcal{C}$ is the sum of the red angles $\alpha_a$ and $\alpha_b$ (the red vectors are tangent to $\mathcal{C}$ at $a$ and $b$).</figcaption></figure>

From the previous lemma, we derive an error bound for any linear interpolation.

**Corollary 7.** Let $\mathcal{C}$ be a plane convex curve. Let $P = [a_i]_{i=0}^m$ ($m \ge 2$) be a linear interpolation of $\mathcal{C}$. Then,

$$ 0 \le \kappa(\mathcal{C}) - \kappa(P) \le \kappa(C_{a_0}^{a_1}) + \kappa(C_{a_{m-1}}^{a_m}). $$

*Proof.* We set $a = a_0$, $b = a_m$. Let us write $\alpha_a$ and $\alpha_b$, resp. $\beta_a$ and $\beta_b$, for the angles between the straight segment $[a, b]$ and the curve $\mathcal{C}$, resp. the polygonal line $P$, at the points $a$ and $b$ (Figure 6 shows the configuration and the notations near the point $a$). The result comes from Lemma 6 applied to the four curves $\mathcal{C}$, $P$, $C_a^{a_1}$ and $C_{a_{m-1}}^b$:

$$ \kappa(\mathcal{C}) = \alpha_a + \alpha_b, \qquad (4) $$

$$ \kappa(P) = \beta_a + \beta_b, \qquad (5) $$

$$ \kappa(C_a^{a_1}) \ge \alpha_a - \beta_a \quad (\text{see Figure 6}), \qquad (6) $$

$$ \kappa(C_{a_{m-1}}^b) \ge \alpha_b - \beta_b. \qquad (7) $$

Subtracting Equation (5) to Equation (4) and using Inequalities (6) and (7) gives the stated result. $\square$
Observe that Corollary 7 is still valid if we allow $m = 1$. In this case it asserts that $\kappa(C) - \kappa(P) \le 2\kappa(C)$, that is $-\kappa(P) \le \kappa(C)$, which is of no interest.

<figure><img src="image_7.png" /><figcaption>**Fig. 6:** Blue, thick: a convex curve $\mathcal{C}$ with endpoint $a$ and $b$ (the point $b$ is outside the figure). Black, thick: the first edge of a polygonal line $P = [a_i]_{i=0}^m$ that interpolates the curve $\mathcal{C}$. Black, thin: the end of the straight segment $[a, b]$. Red: the unit vector right-tangent to $\mathcal{C}$ at $a$ and the unit vector left-tangent to $\mathcal{C}$ at $a_1$. The turn of the arc $C_a^{a_1}$ is the sum of the angle $\alpha_a - \beta_a$ and the green angle at $a_1$. Then, $\kappa(C_a^{a_1}) \ge \alpha_a - \beta_a$.</figcaption></figure>

Provided the convex arc $C_a^b$ has a strongly Lipschitz turn, at least at its ends, Corollary 7 makes it possible to obtain an estimation of the turn of $C_a^b$ with a given precision by using a linear interpolation with sufficiently small edges at its ends (see Section 5.2.2).

### 3.2.2 General case

In the general case, a plane curve can be convex by parts, having infinitely many convex arcs or even having no convex subarc. Figure 7 shows how to modify the Koch curve to obtain a nowhere convex curve with finite turn. Nevertheless, when we want to estimate a geometric feature from acquired data, it is current to make smoothness assumptions on the digitized shape. Here, we will assume the existence of convex subarcs and we will cut the curve in convex parts and remaining parts. Notice that the whole curve does not need to be a plane curve but its convex parts are plane arcs. With this cutting, we aim at obtaining a tighter bound on the estimation error. This implies using some kind of triangle inequality on the error and leads us to propose the notions of *maximal convex arc* and *sewing component*.

Let us now precisely define those maximal convex parts and sewing parts. Let $\mathcal{C}$ be a curve in $E^n$ and $P = [a_i]_{i=0}^m$ be a linear interpolation of $\mathcal{C}$. In the sequel of Section 3, by “curve segment”, we mean an arc of $\mathcal{C}$ between two consecutive vertices of $P$, that is an arc $C_{a_{i-1}}^{a_i}$ where $i \in [1, m]$. A convex arc $C_{a_i}^{a_j}$, $0 \le i \le j - 2 \le m - 2$ is *maximal convex* if $j = m$ or $j < m$ and $C_{a_i}^{a_{j+1}}$ is not convex. Observe that a maximal convex arc must contain at least two curve segments. Otherwise, we could not use the results of Section 3.2.1 about convex curves. By traversing the curve from $a_0$ to $a_m$, we iteratively select the non overlapping maximal convex arcs encountered so that two distinct maximal convex arcs share at most one point. The obtained collection of maximal convex arcs is denoted by $\mathcal{C}^P$. Notice that $\mathcal{C}^P$ may be empty even if the curve
<figure><img src="image_8.png" /><figcaption>Fig. 7: When, starting from a straight segment, we iteratively apply the transformation $\mathcal{T}_1$ with $\theta = \pi/3$ on each edge of the previously produced polygonal line, we get an arc of the Koch curve [35]. Now, instead of applying $\mathcal{T}_1$ at each step, we use $\mathcal{T}_k$ at step $k$. Then the turn of the limit curve is given by a geometric series with common ratio $4\theta$. If $\theta < 1/4$, the curve has a finite turn (equal to $4\theta/(1 - 4\theta)$), thus a finite length, and has no convex subarc.</figcaption></figure>

has convex parts. For instance, if $\mathcal{C}$ is the curve $y = \sin(x)$, $x \in [0, k\pi]$ where $k$ is an integer and if all the vertices of $P$ are on the $x$-axis, then $\mathcal{C}^P = \emptyset$. Also observe that the convex arcs included in $\mathcal{C}^P$ may be different depending on the travel direction (see Figure 8).

Now that we have defined the effective convex part, let us define the other part that we call the *sewing part*. The calculus of the turn requires to cut the curve in overlapping parts and to use the inclusion-exclusion principle (see Lemma 8 and Figure 6). Otherwise, we could miss a turn at some angular point. Hence, we put a *sewing component* between any pair of consecutive maximal convex arcs and between the ends of $\mathcal{C}$ and the first or last maximal convex arc (see Figure 8). More specifically, a sewing component between two consecutive maximal convex arcs $A$ and $B$ is an arc of $\mathcal{C}$ that begins with (and includes) the last curve segment of $A$ and ends with (and includes) the first curve segment of $B$. The sewing component at the beginning of $\mathcal{C}$ is the arc starting at the beginning of $\mathcal{C}$ and including at its end the first curve segment of the first maximal convex arc of $\mathcal{C}^P$. Alike, the sewing component at the end of $\mathcal{C}$ is the arc starting with (and including) the last curve segment of the last maximal convex arc of $\mathcal{C}^P$ and finishing at the end of $\mathcal{C}$. Since a maximal convex arc contains at least two curve segments, two distinct sewing components share at most one point. The collection of all these sewing components is denoted by $\mathcal{C}^P$. Notice that it may happen that $\mathcal{C}^P$ is itself a collection of convex arcs. This is in particular the case when $\mathcal{C}$ is a spiral.

Each maximal convex arc in $\mathcal{C}^P$ overlaps two sewing components. The overlaps are curve segments. We denote by $\mathcal{C}^P \cap \mathcal{C}^P$ the collection of these curve segments. A curve segment is in $\mathcal{C}^P \cap \mathcal{C}^P$ if and only if it is an end of a maximal convex arc of $\mathcal{C}^P$.

Since we cut the curve in overlapping parts, we will use the following equality.

**Lemma 8.** Let $[a, b, c, d]$, $b \neq c$, be an ordered sequence of points on a curve $\mathcal{C}$ of $E^n$ whose turn is finite. Then,

$$ \kappa(\mathcal{C}_a^d) = \kappa(\mathcal{C}_a^c) + \kappa(\mathcal{C}_b^d) - \kappa(\mathcal{C}_b^c). $$

*Proof.* If $a = b$ and $c = d$, the lemma is obvious. We now assume that, for instance, $c \neq d$. Then, $c$ is not an end of the arc $\mathcal{C}_b^d$ and a fortiori of the arc $\mathcal{C}_a^d$. Therefore, according to [9, Theorem 5.1.3 p. 122]

$$ \kappa(\mathcal{C}_a^d) = \kappa(\mathcal{C}_a^c) + \kappa_c + \kappa(\mathcal{C}_c^d), \quad (8) $$
<figure><img src="image_9.png" /><figcaption>Fig. 8: Maximal convex arcs and sewing components relative to a linear interpolation. Top: denoting by $\mathcal{C}$ and $P = [a_i]_{i=0}^{15}$ the curve and its linear interpolation, the “convex part” of $\mathcal{C}$, $\mathcal{C}^P$, is the collection of the four maximal convex arcs depicted in green and orange.</figcaption></figure>

Bottom: the sewing part, $\mathcal{C}^P$, depicted by thick black lines, is composed of five sewing components: $C_{a_0}^{a_1}$, $C_{a_3}^{a_5}$, $C_{a_6}^{a_9}$, $C_{a_{10}}^{a_{12}}$ and $C_{a_{13}}^{a_{15}}$.

Numbering the sample points in the opposite direction would have given another decomposition of $\mathcal{C}$.

where $\kappa_c$ denotes the turn at the point $c$, that is the angle between the left and right unit tangent vectors. Since we also have $\kappa(C_b^d) = \kappa(C_b^c) + \kappa_c + \kappa(C_c^d)$, Equation 8 can be rewritten as

$$ \kappa(C_a^d) = \kappa(C_a^c) + \kappa(C_b^d) - \kappa(C_b^c). \quad \square $$

We conclude this section on the discretization error by showing that $\kappa(C_\sim^P)$ is an upper bound of this error. Hereinafter, we denote by $\kappa(C_\sim^P)$, $\kappa(C_\sim^P)$ and $\kappa(C_\sim^P \cap C_\sim^P)$ the sums of the turns of the arcs that compose the collections $C_\sim^P$, $C_\sim^P$ and $C_\sim^P \cap C_\sim^P$.

**Proposition 9.** Let $\mathcal{C}$ be a curve in $E^n$ with finite turn and $P = [a_i]_{i=0}^m$ be a linear interpolation of $\mathcal{C}$. Then,

$$ 0 \le \kappa(\mathcal{C}) - \kappa(P) \le \kappa(C_\sim^P). \quad (9) $$
<figure><img src="image_10.png" /><figcaption>**Fig. 9:** Left: Formula (10). The curve has two maximal convex arcs, $C_{a_0}^{a_4}$ and $C_{a_4}^{a_8}$ and thus, three sewing components, $C_{a_0}^{a_1}$, $C_{a_3}^{a_5}$ and $C_{a_7}^{a_8}$. The turn $\kappa(C_{a_0}^{a_8})$ can be computed by adding the turns of the two arcs in $C_{\sim}^P$ and the turns of the three arcs in $C_{\sim}^P$. But doing so, the turns of some curve segments are counted twice. Thus, we need to remove them. These curve segments are exactly the arcs that make up $C_{\sim}^P \cap C_{\sim}^P: C_{a_0}^{a_1}, C_{a_3}^{a_4}, C_{a_4}^{a_5}, C_{a_7}^{a_8}$.</figcaption></figure>

Right: Here, the curve is polygonal. Hence, the turns of the curve segments are zero. Then, Formula (10) applied to this polygonal line results in Formula (11).

*Proof.* Thanks to Lemma 8, the turn of $C$ can be split as follows (see Figure 9-left):

$$ \kappa(C) = \kappa(C_{\sim}^P) + \kappa(C_{\sim}^P) - \kappa(C_{\sim}^P \cap C_{\sim}^P). \qquad (10) $$

Let us denote by $P_{\sim}$ and $P_{\sim}$ the (overlapping) parts of $P$ that interpolate respectively $C_{\sim}^P$ and $C_{\sim}^P$. The turns of $P_{\sim}$ and $P_{\sim}$ are the sums of the turns of the polygonal lines $[a_i]_{i=b}^e$ where $b$ is either the beginning of a maximal convex arc or the beginning of a sewing component and $e$ is the end of this maximal convex arc or sewing component.

Since the polygonal line $P$ is broken down so that the last edge of a fragment is the first edge of the next fragment, we have (see Figure 9-right):

$$ \kappa(P) = \kappa(P_{\sim}) + \kappa(P_{\sim}). \qquad (11) $$

Besides, from the turn definition,

$$ 0 \le \kappa(C_{\sim}^P) - \kappa(P_{\sim}) \le \kappa(C_{\sim}^P), \qquad (12) $$

and, thanks to Corollary 7,

$$ 0 \le \kappa(C_{\sim}^P) - \kappa(P_{\sim}) \le \kappa(C_{\sim}^P \cap C_{\sim}^P). \qquad (13) $$

Eventually, subtracting Equation 11 to Equation 10 and using the bounds provided by Equations 12 and 13, we get

$$ 0 \le \kappa(C) - \kappa(P) \le \kappa(C_{\sim}^P). \qquad \square $$
Proposition 9 together with a strongly Lipschitz assumption helps to upper bound
the discretization error when estimating the turn with a polygonal line provided the
curve is an union of, possibly infinitely many, convex arcs (see Section 5.2).

Finally, let us note that all the results obtained in Section 3.2 are easily interpreted using the *tangent indicatrix* also known as *tantrix*. Curves of finite turn are rectifiable and have everywhere left and right tangents [9]. Then, the tantrix is the curve described by the unit tangent vectors of such a curve on the unit sphere $S^{n-1}$ [36, Section 4]. When the left and right tangent vectors differ, they are connected on the tantrix by means of a great circle arc [9, Chapters 3 and 5]. Due to the Mean Value Theorem, the tantrix of a linear interpolation of a curve is a spherical polygonal line inscribed into the tantrix of that curve. If finite, the turn of a curve is equal to the length of its tantrix. Thereby, the discretization error is the difference between the lengths of the two tantrices, the tantrix of the curve and that of the linear interpolation. Convex plane curves have monotonic tantrices on the unit circle. Clearly, the lengths of these tantrices only depend on their ends. Figure 10-left illustrates this situation and makes the link with Corollary 7. Figure 10-right showcases the case of a non-convex plane curve and interprets Proposition 9 thanks to the tantrices.

# 4 Quantization error

Given a curve $\mathcal{C}$ in $E^n$ and a positive real $\epsilon$, we say that a polygonal line $Q = [b_i]_{i=0}^m$
is a *linear $\epsilon$-approximation of $\mathcal{C}$* if there exists a linear interpolation of $\mathcal{C}$, $P = [a_i]_{i=0}^m$
such that $\|a_i - b_i\| \le \epsilon$ for any $i \in [0, m]$. We say that a polygonal line $Q$ is a
*linear approximation of $\mathcal{C}$* if $Q$ is a linear $\epsilon$-approximation of $\mathcal{C}$ for some $\epsilon > 0$. When
estimating the turn of $\mathcal{C}$, the *quantization error* is the difference between the turn of
a linear approximation of $\mathcal{C}$ and the turn of the related linear interpolation.

Firstly, we compare the turn of two elementary polygonal lines, only having three
vertices, and then we extend the result to any pair of polygonal lines.

## 4.1 Elementary error

Let us introduce new notations. Given a positive real $r$ and points $x, y, z$ in $E^n$, we
denote by $B_r(x)$ the closed ball of center $x$ and radius $r$ and we denote by $\angle_x(y, z)$
the angle at $x$ in the triangle $xyz$, that is the angle between the vectors $\vec{x}y$ and $\vec{x}z$.

Let $\epsilon > 0$. We consider three balls in $E^n$ with radius $\epsilon$ and centers $a, b, c$ and three points $a', b', c'$ belonging respectively to these three balls: $a' \in B_\epsilon(a)$, $b' \in B_\epsilon(b)$, $c' \in B_\epsilon(c)$. In order to upper bound the difference between the turn of the polygonal line $[a, b, c]$ and the turn of the polygonal line $[a', b', c']$, that is the difference $|\angle_b(a, c) - \angle_{b'}(a', c')|$, we consider two pairs of tangents shared by the circles $\partial B_\epsilon(a)$ and $\partial B_\epsilon(b)$ on the one hand and the circles $\partial B_\epsilon(c)$ and $\partial B_\epsilon(b)$ on the other hand. The slopes of these tangents bound the slopes of both sides of the angle $\angle_{b'}(a', c')$ (see Figure 11). This gives an easy, but not optimal, upper-bound. Indeed, in the general case, the line segments $[a', b']$ and $[b', c']$ cannot be both tangent to the circle $\partial B_\epsilon(b)$. In other words, the point $z$ in Figure 11 is outside the circle $\partial B_\epsilon(b)$. Nevertheless, as the edge lengths of the linear interpolations tends towards zero, and provided the curve is sufficiently regular, that is its turn is strongly Lipschitz, the turns of the interpolations
<figure><img src="image_11.png" /><figcaption>**Fig. 10:** Tantrices. Left: The circle arc from $a_0$ to $a_4$ is the tantrix of a plane convex curve $C$. The circle arc from $b_0$ to $b_3$ is the tantrix of a linear interpolation $P$ of $C$. The points $a_i$ correspond to the unit tangent vectors of $C$ at the vertices of $P$ whereas the points $b_j$ correspond to the edge directions of $P$. Corollary 7 asserts that the difference between the lengths of the two circular arcs is upper bounded by the sum of the lengths of the arcs from $a_0$ to $a_1$ and from $a_3$ to $a_4$. Right: The circle arc from $a_0$ to $a_m$ is the tantrix $T$ of a plane non convex curve $C$. Since $C$ is non convex, $T$ is non simple. We use an artificial dashed blue line to show how $T$ is traveled. The circle arc from $b_0$ to $b_{m-1}$ is the tantrix of a linear interpolation of $C$. The dashed red line shows how this latter tantrix is traveled. The blue points $a_i$ and the red points $b_j$ are defined in the same way as in the figure on the left. Proposition 9 asserts that the difference between the two circular arcs are upper bounded by the sum of the lengths of, on the one hand, the ends of $T$, $T_{a_0}^{a_1}$ and $T_{a_{m-1}}^{a_m}$ and, on the other hand, the U-turns of $T$, $T_{a_i}^{a_{i+3}}$ and $T_{a_j}^{a_{j+3}}$.</figcaption></figure>

at their vertices vanish. Furthermore, optimal choices for the ratio linear interpolation edge length to $\epsilon$ make the ratio tend towards infinity as $\epsilon \to 0$ (see Section 5). In this case, the point $z$ of Figure 11 tends towards the circle $\partial B_\epsilon(b)$ making the proposed upper bound more and more tight.

Looking at Figure 11, upper bounding the difference between the turns of the polygonal lines $[a, b, c]$ and $[a', b', c']$ should be easily geometrically handled. But, there is many other geometric contingencies and it is not easy to be sure not to forget a specific case. That is why our proof moves away from intuition to use a more formal way.

First, let us state two properties of right circular solid vector cones. We denote by $V^n$ the vector space associated to $E^n$. The right circular solid vector cone of axis $u \in V^n$ and aperture $2\theta \in [0, \pi]$ is the set of vectors $v \in V^n$ such that the angle $\alpha \in [0, \pi]$ between $u$ and $v$ is at most $\theta$.
<figure><img src="image_12.png" /><figcaption>**Fig. 11:** The three circles have the same radius. Lemma 12 states that the difference between the curvature of the polygonal line [a', b', c'] (in green) and the curvature of the polygonal line [a, b, c] (in red and blue) is at most the sum of the angles $\theta_a$ and $\theta_c$.</figcaption></figure>

**Lemma 10.** Let $\mathbf{u}$ be a unit vector of $V^n$ and $\theta \in [0, \pi/2]$. Let $\mathbf{a}$ and $\mathbf{b}$ be two vectors belonging respectively to the right circular solid vector cones with aperture $2\theta$ and axes $\mathbf{u}$ and $-\mathbf{u}$. Then, the vector $\mathbf{a} - \mathbf{b}$ belongs to the solid vector cone with axis $\mathbf{u}$ and aperture $2\theta$.

*Proof.* If $\mathbf{a} = \mathbf{b}$, the result is obvious. From now on, we assume $\mathbf{a} \neq \mathbf{b}$. In the limit case $\theta = \pi/2$, denoting by $p$ the linear projection from $V^n$ to the line $Ru$, the hypotheses are $\langle p(\mathbf{a})|\mathbf{u} \rangle \ge 0$ and $\langle p(\mathbf{b})|\mathbf{u} \rangle \le 0$. Then, $\langle p(\mathbf{a} - \mathbf{b})|\mathbf{u} \rangle \ge 0$ which is the desired result. Now, assuming $\theta < \pi/2$, we derive from the main hypotheses that there exist four real numbers $\lambda_a, \lambda_b, \mu_a, \mu_b$ and two unit vectors $\mathbf{v}, \mathbf{w}$ orthogonal to the vector $\mathbf{u}$ such that

$$ \mathbf{a} = \lambda_a \mathbf{u} + \mu_a \tan(\theta) \mathbf{v} \quad \text{and} \quad \mathbf{b} = \lambda_b \mathbf{u} + \mu_b \tan(\theta) \mathbf{w}, $$

where $|\mu_a| \le |\lambda_a|, |\mu_b| \le |\lambda_b|, \lambda_a \ge 0$ and $\lambda_b \le 0$.

Let $\theta_{a,b}$ be the (unoriented) angle between the vector $\mathbf{u}$ and the vector $\mathbf{a} - \mathbf{b}$. We have,

$$ \cos(\theta_{a,b}) = \frac{\langle \mathbf{a} - \mathbf{b} | \mathbf{u} \rangle}{\|\mathbf{a} - \mathbf{b}\| \|\mathbf{u}\|} = \frac{\lambda_a - \lambda_b}{\sqrt{(\lambda_a - \lambda_b)^2 + \tan^2(\theta) N^2}}, $$

where $N = \|\mu_a \mathbf{v} - \mu_b \mathbf{w}\| \le |\mu_a| + |\mu_b| \le |\lambda_a| + |\lambda_b| = \lambda_a - \lambda_b$. Then,

$$ \cos(\theta_{a,b}) \ge \frac{1}{\sqrt{1 + \tan^2(\theta)}} = \cos(\theta). $$

We derive that $0 \le \theta_{a,b} \le \theta$, that is, $\mathbf{a} - \mathbf{b}$ belongs to the solid cone with aperture $2\theta$ and axis $\mathbf{u}$. $\square$

**Lemma 11.** Let $C_1$, resp. $C_2$, be a right circular solid vector cone of $V^n$ whose axis is directed by the unit vector $\mathbf{u}_1$, resp. $\mathbf{u}_2$, and whose aperture is $2\theta_1$, resp. $2\theta_2$, with
$\theta_1$, resp. $\theta_2$, $\in [0, \pi/2]$. Then, for any $\mathbf{v}_1 \in C_1$, $\mathbf{v}_2 \in C_2$,

$$|\angle(\mathbf{v}_1, \mathbf{v}_2) - \angle(\mathbf{u}_1, \mathbf{u}_2)| \le \theta_1 + \theta_2.$$

*Proof.* Thanks to the triangle inequality for angles of vectors [37], one has

$$\angle(\mathbf{u}_1, \mathbf{u}_2) \le \angle(\mathbf{u}_1, \mathbf{v}_1) + \angle(\mathbf{v}_1, \mathbf{v}_2) + \angle(\mathbf{v}_2, \mathbf{u}_2),$$

that is,

$$\angle(\mathbf{u}_1, \mathbf{u}_2) - \angle(\mathbf{v}_1, \mathbf{v}_2) \le \angle(\mathbf{u}_1, \mathbf{v}_1) + \angle(\mathbf{v}_2, \mathbf{u}_2),$$

and

$$\angle(\mathbf{v}_1, \mathbf{v}_2) \le \angle(\mathbf{v}_1, \mathbf{u}_1) + \angle(\mathbf{u}_1, \mathbf{u}_2) + \angle(\mathbf{u}_2, \mathbf{v}_2),$$

that is

$$\angle(\mathbf{v}_1, \mathbf{v}_2) - \angle(\mathbf{u}_1, \mathbf{u}_2) \le \angle(\mathbf{v}_1, \mathbf{u}_1) + \angle(\mathbf{u}_2, \mathbf{v}_2).$$

Since $\angle(\mathbf{u}_1, \mathbf{v}_1)$ and $\angle(\mathbf{v}_2, \mathbf{u}_2)$ are respectively upper bounded by $\theta_1$ and $\theta_2$, we get

$$|\angle(\mathbf{v}_1, \mathbf{v}_2) - \angle(\mathbf{u}_1, \mathbf{u}_2)| \le \theta_1 + \theta_2. \quad \square$$

Thanks to the preceding lemmas, we can now bound the quantization error in the basic case of a linear $\epsilon$-approximation having only three vertices.

**Lemma 12.** Let $\epsilon > 0$ and $a, b, c$ in $E^n$ such that $\|b-a\|$ and $\|c-b\|$ are both greater than or equal to $2\epsilon$. Then, for any $a' \in B_\epsilon(a)$, $b' \in B_\epsilon(b)$ and $c' \in B_\epsilon(c)$,

$$|\kappa([a', b', c']) - \kappa([a, b, c])| \le \arcsin \frac{2\epsilon}{\|b-a\|} + \arcsin \frac{2\epsilon}{\|b-c\|}.$$

*Proof.* Let $m$ and $n$ be the midpoints of the line segments $[ba]$ and $[bc]$. From Lemma 10, the vectors $a' - b'$ and $c' - b'$ respectively belong to the solid vector cones $C_a$ and $C_c$, with axis $\mathbf{u}_a = a - m$ and aperture $2\theta_a = 2\arcsin \frac{2\epsilon}{\|b-a\|}$ for the former and with axis $\mathbf{u}_b = c - n$ and aperture $2\theta_c = 2\arcsin \frac{2\epsilon}{\|b-c\|}$ for the latter (see Figure 11). Thanks to Lemma 11, we derive that

$$|\angle_{b'}(a', c') - \angle(\mathbf{u}_a, \mathbf{u}_b)| \le \theta_a + \theta_c.$$

Since $\angle_{b'}(a', c') = \pi - \kappa([a', b', c'])$ and $\angle(\mathbf{u}_a, \mathbf{u}_b) = \angle_b(a, c) = \pi - \kappa([a, b, c])$, we obtain

$$|\kappa([a', b', c']) - \kappa([a, b, c])| \le \theta_a + \theta_c. \quad \square$$

## 4.2 Global quantization error

Applying Lemma 12 at each of the non terminal vertices of an $\epsilon$-approximation yields a quantization error upper bound.
**Proposition 13.** Let $\epsilon$ be a positive real and $P = [p_i]_{i=0}^m$, $Q = [q_i]_{i=0}^m$ be two polygonal lines in $E^n$ such that $d(p_i, q_i) \le \epsilon$ for any $i \in [0, m]$ ($m > 0$). Let $\ell$ be the minimum length of the edges of $Q$. If $\ell \ge 2\epsilon$, then

$$|\kappa(P) - \kappa(Q)| \le (2m - 2) \arcsin \frac{2\epsilon}{\ell}.$$

*Proof.* We apply Lemma 12 at each vertex $q_i$, $1 \le i \le m - 1$. □

# 5 Convergence of naive turn estimators

In this section, we prove the convergence of the total curvature naive estimators in the case of simple curves and we compute the convergence speeds under various assumptions. We will use the following asymptotic notations: Big O, Little O, Big Omega (the inverse of Big O) and Little Omega (the inverse of Little O), see [38].

## 5.1 Simple curves

Given a polygonal line $P$, we denote by $\mu(P)$ the length of its smaller side (recall that $\lambda(P)$ denotes the length of its longest side).

To ensure that both the discretization error and the quantization error vanish as $\epsilon \to 0$, the edge lengths of the naive turn estimators need to obey laws that may seem antagonistic. Reducing the discretization error implies decreasing these lengths whereas reducing the quantization error implies increasing —with respect to the $\epsilon$ parameter— the same lengths. Let us first look at the quantization error. The following lemma provides a simple ratio that dominates as $\epsilon \to 0$ the difference between the turn of an $\epsilon$-approximation and the turn of an associated linear interpolation.

**Lemma 14.** Let $C$ be a simple curve in $E^n$. Let $(Q_\epsilon)_{\epsilon>0}$ be a family of linear $\epsilon$-approximations of $C$. If the minimum edge length $\mu(Q_\epsilon)$ of $Q_\epsilon$ is such that $\mu(Q_\epsilon) \in \omega(\epsilon)$, then, for any family $(P_\epsilon)_{\epsilon>0}$ of linear interpolations of $C$ whose vertices are at distance at most $\epsilon$ from the vertices of $Q_\epsilon$,

$$|\kappa(P_\epsilon) - \kappa(Q_\epsilon)| = O\left(\frac{\epsilon}{\mu(Q_\epsilon)^2}\right).$$

*Proof.* Let $(P_\epsilon)_{\epsilon>0}$ be a family of linear interpolations whose vertices are at distance at most $\epsilon$ from the vertices of $Q_\epsilon$. From the hypotheses, we have

$$\frac{\epsilon}{\mu(Q_\epsilon)} = o(1) \quad \text{as } \epsilon \to 0.$$

Then, for sufficiently small $\epsilon$, the hypothesis $\mu(Q_\epsilon) \ge 2\epsilon$ of Proposition 13 is satisfied and,

$$|\kappa(P_\epsilon) - \kappa(Q_\epsilon)| \le (2m - 2) \arcsin \frac{2\epsilon}{\mu(Q_\epsilon)},$$
where $m$ is the edge number of $Q_\epsilon$. Since $\arcsin(x) \sim x$ as $x \to 0$, we derive that

$$|\kappa(P_\epsilon) - \kappa(Q_\epsilon)| = O\left(\frac{m\epsilon}{\mu(Q_\epsilon)}\right). \qquad (14)$$

Besides, denoting by $\mathcal{L}(\cdot)$ the length, we have

$$m \times \mu(P_\epsilon) \le \mathcal{L}(P) \le \mathcal{L}(C).$$

Hence,

$$m \in O\left(\frac{1}{\mu(P_\epsilon)}\right) \subset O\left(\frac{1}{\mu(Q_\epsilon)}\right).$$

By substituting $O(\frac{1}{\mu(Q_\epsilon)})$ to $m$ in (14), we get the result:

$$|\kappa(P_\epsilon) - \kappa(Q_\epsilon)| = O\left(\frac{\epsilon}{\mu(Q_\epsilon)^2}\right). \qquad \square$$

We can now obtain sufficient conditions so that naive turn estimates tend towards the right value as $\epsilon \to 0$.

**Proposition 15.** Let $C$ be a simple curve in $E^n$. Let $(Q_\epsilon)_{\epsilon>0}$ be a family of linear $\epsilon$-approximations of $C$. If the maximum edge length $\lambda(Q_\epsilon)$ of $Q_\epsilon$ tends to 0 as $\epsilon \to 0$ and the minimum edge length $\mu(Q_\epsilon)$ of $Q_\epsilon$ is such that $\mu(Q_\epsilon) \in \omega(\epsilon^{1/2})$, then

$$\lim_{\epsilon \to 0} \kappa(Q_\epsilon) = \kappa(C).$$

*Proof.* For any $\epsilon > 0$, there exists a linear interpolation, which we denote by $P_\epsilon$, whose vertices are at distance at most $\epsilon$ from the vertices of $Q_\epsilon$. Then,

$$|\lambda(P_\epsilon) - \lambda(Q_\epsilon)| \le 2\epsilon.$$

Since, by hypothesis, $\lambda(Q_\epsilon) \to 0$ as $\epsilon \to 0$, we derive

$$\lim_{\epsilon \to 0} \lambda(P_\epsilon) = 0,$$

and, according to Corollary 5,

$$\lim \kappa(P_\epsilon) = \kappa(C). \qquad (15)$$

Furthermore, according to Lemma 14,

$$|\kappa(P_\epsilon) - \kappa(Q_\epsilon)| = O\left(\frac{\epsilon}{\mu(Q_\epsilon)^2}\right).$$

Taking into account the hypothesis $\mu(Q_\epsilon) \in \omega(\epsilon^{1/2})$, we get

$$|\kappa(P_\epsilon) - \kappa(Q_\epsilon)| = o(1), \qquad (16)$$
Eventually, from Equations (15) and (16), we conclude straightforwardly:

$$ \lim_{\epsilon \to 0} \kappa(Q_{\epsilon}) = \kappa(C). \quad \square $$

Examining the proof of Proposition 15, we can see that it is sufficient to assume $\mu(Q_{\epsilon}) \in \Omega(\epsilon^{1/2})$ to decide whether $\kappa(C) = \infty$ or $\kappa(C) < \infty$ (for $\infty + O(1) = \infty$). Nevertheless, we need the assumption $\mu(Q_{\epsilon}) \in \omega(\epsilon^{1/2})$ to obtain the correct limit when $\kappa(C) < \infty$.

The simpleness assumption being too weak to allow convergence speed estimation, we examine in the remainder of this section some examples of concatenations of convex plane arcs whose turns are strongly Lipschitz, at least near the end of the arcs.

## 5.2 Simple curves with finite and Lipschitz turn

In order to upper bound the difference between a naive turn estimation and the true turn value, we need to add a regularity assumption to the simpleness hypothesis on curves. In Section 1, we introduced the notion of strongly Lipschitz turn and justified its use in this work. Recall that a curve has a strongly Lipschitz turn if its turn is Lipschitz with respect to the Euclidean distance, that is, if there exists a real $k > 0$ such that, for any points $a, b \in C$, $\kappa(C_a^b) \le k\|a - b\|$. Since the turn of a convex arc only depends on the direction of the curve at its ends (Lemma 6), in the best case (finite concatenations of convex arcs) we only need the strongly Lipschitz property near the ends of the convex subarcs of the curve. Hence, given a positive real $k$, we say that a curve $C$ has a $k$-strongly Lipschitz turn at $a \in C$ if $C$ is smooth at $a$ and there exists a positive real $r$ such that $\kappa(C_a^b) \le k\|a - b\|$ for any $b \in C \cap B_r(a)$. We start by a general result about the order of convergence of the discretization error and then we will deduce lower bounds for the naive estimator convergence speed when applied to curves that are composed of convex arcs.

### 5.2.1 Discretization error convergence order

**Lemma 16.** Let $C$ in $E^n$ be a simple curve of finite turn and $(P_{\epsilon})_{\epsilon>0}$ be a family of linear interpolations of $C$. If, for some positive $k$ and for sufficiently small $\epsilon$, the turn of $C$ is $k$-strongly Lipschitz on each sewing component of $C_{\sim}^{P_{\epsilon}}$, then

$$ \kappa(C) - \kappa(P_{\epsilon}) \le k n_{\epsilon} \lambda(P_{\epsilon}), $$

where $n_{\epsilon}$ denotes the number of edges of $P_{\epsilon}$ that interpolate an arc of $C_{\sim}^{P_{\epsilon}}$. In particular, if $\lambda(P_{\epsilon}) \in O(\epsilon^{\beta})$ where $\beta$ is a positive real, then

$$ \kappa(C) - \kappa(P_{\epsilon}) \in n_{\epsilon} O(\epsilon^{\beta}). $$

*Proof.* Let $k > 0$ and $\epsilon_0 > 0$ such that the turn of $C$ is $k$-strongly Lipschitz on each sewing component of $C_{\sim}^{P_{\epsilon}}$ where $0 < \epsilon < \epsilon_0$. Thanks to Proposition 9,

$$ \kappa(C) - \kappa(P_{\epsilon}) \le \kappa(C_{\sim}^{P_{\epsilon}}). $$
For any $\epsilon \in (0, \epsilon_0)$, the components of $C_{\sim}^{P_\epsilon}$ are smooth for the turn $C$ is $k$-Lipschitz on $C_{\sim}^{P_\epsilon}$ (Proposition 20). Thereby,

$$ \kappa(C_{\sim}^{P_\epsilon}) = \sum_{S \in C_{\sim}^{P_\epsilon}} \sum_{\kappa(C_{a_{i-1}}^{a_i}) | C_{a_{i-1}}^{a_i} \subset S} \{\kappa(C_{a_{i-1}}^{a_i}) | C_{a_{i-1}}^{a_i} \subset S\}, $$

where $a_0, \dots, a_m$ are the vertices of $P_\epsilon$. Since $\kappa$ is $k$-strongly Lipschitz on $C_{\sim}^{P_\epsilon}$, we derive

$$ \kappa(C_{\sim}^{P_\epsilon}) \le k \sum_{S \in C_{\sim}^{P_\epsilon}} \sum_{\|a_{i-1} - a_i\| | C_{a_{i-1}}^{a_i} \subset S} \{\|a_{i-1} - a_i\| | C_{a_{i-1}}^{a_i} \subset S\} \le k n_\epsilon \lambda(P_\epsilon). $$

If, furthermore, $\lambda(P_\epsilon) \in O(\epsilon^\beta)$, we get

$$ \kappa(C_{\sim}^{P_\epsilon}) \in n_\epsilon O(\epsilon^\beta). \quad \square $$

### 5.2.2 Convex arcs

The case of convex curves is very particular. Indeed, we saw in Section 3.2.1 that, for estimating the turn, only the ends of the curve matter. Then, the number of edges of the polygonal approximations need not increase when $\epsilon \to 0$. On the contrary, the smaller the number of edges, the smaller the quantization error, especially since a polygonal approximation of a convex curve needs not be convex<fnref n="5" />.

**Proposition 17.** Let $C$ be a plane convex curve whose turn is strongly Lipschitz at its ends. Let $(Q_\epsilon)_{\epsilon>0} = ([a_0^\epsilon, a_1^\epsilon, a_2^\epsilon, a_3^\epsilon])_{\epsilon>0}$ be a family of linear $\epsilon$-approximations of $C$. If $\|a_0^\epsilon - a_1^\epsilon\|$ and $\|a_2^\epsilon - a_3^\epsilon\|$ are both in $\Omega(\epsilon^\alpha) \cap O(\epsilon^\beta)$ with $0 < \beta \le \alpha < 1$, then

$$ \kappa(C) - \kappa(Q_\epsilon) = O(\epsilon^\beta) + O(\epsilon^{1-\alpha}). $$

In particular, the best convergence speed is obtained taking $\alpha = \beta = \frac{1}{2}$.

*Proof.* Let $(P_\epsilon)_{\epsilon>0}$ be a family of linear interpolations of $C$ associated to the $\epsilon$-approximations $Q_\epsilon$. On the one hand, thanks to Proposition 13 and the hypotheses, we have

$$ |\kappa(P_\epsilon) - \kappa(Q_\epsilon)| = O(\epsilon^{1-\alpha}). \quad (17) $$

On the other hand, thanks to Lemma 16, we know that

$$ |\kappa(C) - \kappa(P_\epsilon)| = O(\epsilon^\beta). \quad (18) $$

By adding both previous equations, we get the result. $\square$

### 5.2.3 Finite concatenations of convex arcs

When the curve is supposed to be a finite concatenations of convex arcs, but the locations and perhaps even the number of convex subarcs are unknown, we cannot use Proposition 17 to upper bound the turn estimation error. Another upper bound should

<footnote n="5">⁵See [39, Appendix A.2] which exhibits a parabola whose representation on pixel grids is generally not convex.</footnote>
be use instead. Indeed, Proposition 17 assumes an adequate linear approximation which cannot be found in the general case of a convex arc finite concatenation.

**Proposition 18.** Let $\mathcal{C}$ be a curve in $E^n$ which is a finite concatenation of convex plane arcs and whose turn is strongly Lipschitz at the ends of $\mathcal{C}$ and at each gluing point. Let $(Q_\epsilon)_{\epsilon>0}$ be a family of linear $\epsilon$-approximations of $\mathcal{C}$. If the minimum and maximum edge lengths $\mu(Q_\epsilon)$ and $\lambda(Q_\epsilon)$ are such that $\mu(Q_\epsilon) \in \Omega(\epsilon^\alpha)$ and $\lambda(Q_\epsilon) \in O(\epsilon^\beta)$ with $0 < \beta \le \alpha < 1/2$, then

$$ \kappa(\mathcal{C}) - \kappa(Q_\epsilon) = O(\epsilon^\beta) + O(\epsilon^{1-2\alpha}). $$

In particular, the best convergence speed is obtained taking $\alpha = \beta = \frac{1}{3}$.

*Proof.* Let $(P_\epsilon)_{\epsilon>0}$ be a family of linear interpolations of $\mathcal{C}$ associated to $(Q_\epsilon)_{\epsilon>0}$. Then, $\lambda(P_\epsilon) \in O(\epsilon^\beta)$. Since $\mathcal{C}$ is a finite concatenation of convex arcs —say $m$ convex arcs ($m \ge 2$), its turn is finite. Indeed, the turn of each convex arc is at most $2\pi$ [9, Theo. 5.1.5, p. 125] and a convex arc having right and left tangent everywhere, the turn at each point of concatenation is well-defined and at most $2\pi$. Thereby, the turn of $\mathcal{C}$ is at most $(4m-2)\pi$. The turn of $\mathcal{C}$ being finite, we derive from Lemma 16 that

$$ \kappa(\mathcal{C}) - \kappa(P_\epsilon) = n_\epsilon O(\epsilon^\beta), $$

where $n_\epsilon$ is the number of edges of $P_\epsilon$ that interpolate an arc of $C_{\sim}^{P_\epsilon}$. By definition of $C_{\sim}^{P_\epsilon}$, the value of $n_\epsilon$ is at most three times the value of $m$ (see Figure 8). Since $m$ is a constant, we derive an upper bound of the discretization error convergence order:

$$ \kappa(\mathcal{C}) - \kappa(P_\epsilon) = O(\epsilon^\beta). \qquad (19) $$

We bound the quantization error thanks to Lemma 14 and the hypothesis $\mu(Q_\epsilon) \in \Omega(\epsilon^\alpha)$:

$$ \kappa(P_\epsilon) - \kappa(Q_\epsilon) = O(\epsilon^{1-2\alpha}). \qquad (20) $$

Eventually, adding Equations (19) and (20), we get the result:

$$ \kappa(\mathcal{C}) - \kappa(Q_\epsilon) = O(\epsilon^\beta) + O(\epsilon^{1-2\alpha}). \quad \square $$

### 5.2.4 Example of infinite concatenation of convex arcs

In this section, we do not give a general result. We just give an example with a curve that contain an accumulation point for the changes of convexity.

We consider the real-valued function $f$ defined on $[0, 1]$ by $f(0) = 0$ and, for any $x \ne 0$, by $f(x) = x^\eta \sin(\pi/x)$ where $\eta \ge 4$ so that $f$ is of class $C^{1,1}$. We denote by $\mathcal{C}$, the graph of $f$. Since $f$ is of class $C^{1,1}$, the turn of $\mathcal{C}$ is strongly Lipschitz (Proposition 20) and finite [9, Theorem 5.4.3].

Let $\epsilon > 0$ and $P_\epsilon$ be a linear interpolation of $\mathcal{C}$ whose maximum edge length, $\lambda(P_\epsilon)$, is in $O(\epsilon^\beta)$ where $\beta \in (0, 1)$. In order to upper bound $\kappa(C_{\sim}^{P_\epsilon})$, we do not use directly Lemma 16. Instead, we firstly split the curve $\mathcal{C}$ into two parts, $C_o^{c_\epsilon}$ and $C_{c_\epsilon}^e$ where $o$
and $e$ are the left and right ends of $C$ and $c_e$ is an inner point of the curve chosen among the vertices of $P_e$ (see Figure 12). We denote by $x_e$ the abscissa of the point $c_e$ and by $P_e^l$ and $P_e^r$ the parts of $P_e$ that interpolate respectively $C_o^{c_e}$ and $C_{c_e}^e$.

<figure><img src="image_13.png" /><figcaption>Fig. 12: The graph $C$ of $f(x) = x^4 \sin(\pi/x)$, $x \in [0, 1]$. Left: the left part of $C$, $C_o^{c_e}$ where the abscissa of $c_e$ is 0.1 and the scale of the $y$-axis is 1000 times that of the $x$-axis. Right: the right part of $C$, $C_{c_e}^e$. The $x$-axis and the $y$-axis have the same scale.</figcaption></figure>

On the left arc $C_o^{c_e}$, there are so much inflection points that, likely, the subarcs of $C$ interpolated by the edges of $P_e$ contain at least one inflection point. Hence, we just use the Lipschitz hypothesis:

$$ \kappa(C_o^{c_e}) - \kappa(P_e^l) \le \kappa(C_o^{c_e}) \le k\sqrt{2}x_e, $$

where $k$ is the Lipschitz parameter. The factor $\sqrt{2}$ stems from the inequality $\|c_e - o\| \le \sqrt{2}x_e$. Thereby, we have:

$$ \kappa(C_o^{c_e}) - \kappa(P_e^l) = O(x_e). \qquad (21) $$

In the right part, there is a finite number of convexity changes and for sufficiently small $\epsilon$ there are only a few subarcs of $C$ interpolated by the edges of $P_e$ that contain an inflection point. Then, we apply Lemma 16:

$$ \kappa(C_{c_e}^e) - \kappa(P_e^r) \le k n_e \lambda(P_e), $$

where $n_e$ denotes the number of edges of $P_e$ that interpolate an arc of $C_{\sim_e}^{P_e} \cap C_{c_e}^e$. By the definition of $C_{\sim_e}^{P_e}$, the value of $n_e$ is at most 3 times the number of inflection points on $C_{c_e}^e$. Moreover, to within one unit, the number of inflection points in the arc $C_{c_e}^e$ is the number of intersections between the arc and the abscissa axis, that is about $1/x_e$. Then, using the hypothesis $\lambda(P_e) \in O(\epsilon^\beta)$,

$$ \kappa(C_{c_e}^e) - \kappa(P_e^r) \in O(x_e^{-1} \epsilon^\beta). \qquad (22) $$
Since $\mathcal{C}$ is smooth, we derive from Equations 21 and (22) that

$$ \kappa(\mathcal{C}) - \kappa(P_{\epsilon}) = O(x_{\epsilon}) + O(x_{\epsilon}^{-1}\epsilon^{\beta}). \qquad (23) $$

Equation (23) is valid for any $x_{\epsilon} \in (0, 1)$. The best choice is to take $x_{\epsilon} \approx x_{\epsilon}^{-1}\epsilon^{\beta}$ which gives $x_{\epsilon} \in \Theta(\epsilon^{\beta/2})$ —which is compatible with the fact that $c_{\epsilon}$ is chosen among the vertices of $P_{\epsilon}$— Then,

$$ \kappa(\mathcal{C}) - \kappa(P_{\epsilon}) = O(\epsilon^{\beta/2}). \qquad (24) $$

Eventually, adding the quantification error, we conclude that, given a family $(Q_{\epsilon})_{\epsilon>0}$ of linear $\epsilon$-approximations of $\mathcal{C}$ whose minimum and maximum edge lengths $\mu(Q_{\epsilon})$ and $\lambda(Q_{\epsilon})$ are such that $\mu(Q_{\epsilon}) \in \Omega(\epsilon^{\alpha})$ and $\lambda(Q_{\epsilon}) \in O(\epsilon^{\beta})$ with $0 < \beta \le \alpha < 1/2$, we have

$$ \kappa(\mathcal{C}) - \kappa(Q_{\epsilon}) = O(\epsilon^{\beta/2}) + O(\epsilon^{1-2\alpha}). $$

In particular, the best convergence speed is $O(\epsilon^{1/5})$ obtained taking $\alpha = \beta = \frac{2}{5}$.

## 6 Tests

Let us present a set of turn estimations for three plane curves. The first curve is an arc of focal circular cubic whose Cartesian equation is $(x-2)(x^2+y^2)+4y=0$ with $x \le 2, y \le 2+\sqrt{3}$. The curve has two inflection points. The second curve is an arc of spiral whose polar equation is $\rho = \theta/10$, where $\theta \in [0, 4\pi]$. It is not convex though it has no inflection point. The last curve belongs to the family studied in Section 5.2.4. For the experiment, we took the curve $x \mapsto x^4 \sin(\pi/x)$ with $x \in [0, 1]$. It is of class $C^{1,1}$, thus it is of finite turn, and has infinitely many inflection points. The three curves are depicted in Figure 13.

<figure><img src="image_14.png" /><figcaption>Fig. 13: The three curves on which the naive turn estimators are tested. Their turns are numerically calculated by integrating their differential curvatures. Then, these turns are estimated by means of $\epsilon$-linear approximations with $\epsilon$ decreasing from 0.05 to about $5e^{-9}$ and with edge sizes belonging to $\Theta(\epsilon^{\alpha})$ where $\alpha \in \{\frac{1}{4}, \frac{1}{3}, \frac{2}{5}, \frac{1}{2}\}$.</figcaption></figure>

For each curve, we compute 4 sequences of $\epsilon$-approximations. In a given sequence, the edge lengths of the polygonal approximations belong to $\Theta(\epsilon^{\alpha})$ where $\alpha$ is one of $\{\frac{1}{4}, \frac{1}{3}, \frac{2}{5}, \frac{1}{2}\}$. The values of $\epsilon$ are $2^{-k}/10, 1 \le k \le 24$. The vertices of the polygonal
approximations are obtained by moving the sample points towards the grid $\epsilon\mathbb{Z}^2$ by means of floor functions. Eventually, for each $\epsilon$-approximation, we calculate

1. the discretization error, that is the difference between the turn of the curve and the turn of a curve interpolation associated to the given linear approximation;

2. the absolute quantization error, that is the absolute difference between the turn of the $\epsilon$-approximation and the turn of its associated curve interpolation;

3. the global error, that is the difference between the turn of the curve and the turn of the $\epsilon$-approximation.

The results are gathered in Table 2.

<table><caption>**Table 2:** Errors in naive turn estimations in function of the inverse of the precision parameter $\epsilon$. The parameter $\alpha$ controls the edge sizes of the polygonal lines used by the estimator: the minimum and maximum edge lengths belong to $\Theta(\epsilon^\alpha)$.</caption><thead><tr><th></th><th>Discretization error</th><th>Quantization error</th><th>Total error</th></tr></thead><tbody><tr><td>Focal cubic</td><td></td><td></td><td></td></tr><tr><td>Spiral</td><td></td><td></td><td></td></tr><tr><td>Damped sinusoid</td><td></td><td></td><td></td></tr></tbody></table>

Let us now examine the test results against the error upper bounds found in Section 5.2. The observed convergence orders are given in Table 3. In our test, we
use $\epsilon$-linear approximations with edge lengths in $\Theta(\epsilon^\alpha)$. Hence, we have to look at formulas of Sections 5.2.3 and 5.2.4 taking $\beta = \alpha$.

* Regarding the discretization error, the calculated convergence order lower bound is $\alpha$ for the cubic curve and the spiral (Formula 19) and $\alpha/2$ for the sinusoidal curve (Formula 24). The observed results fit these lower bounds. Note that the scatter plots for the third curve are slightly concave indicating that the coefficient in front of $\epsilon^{\alpha/2}$ increases (towards some finite limit) as $\epsilon$ goes to zero. We could not explain this behavior.

* Regarding the quantization error, data points are more scattered around the linear model. Furthermore, the convergence speed is generally much better than our lower bound, which is $1 - 2\alpha$, except for $\alpha = \frac{1}{2}$. Actually, when we evaluated the upper bound in Section 4, we placed ourselves in the worst case scenario in which each turn at a linear approximation vertex increases the difference between the curve turn and the interpolation turn. It is likely that it is rarely the case (though it can occurs, for instance if a straight segment is approximated by a staircase function).

* Finally, at the tested values of the parameter $\epsilon$, the quantization error is several order of magnitude smaller than the discretization error. This results in a total error which is generally better with smaller linear approximation edge lengths that is, larger values of $\alpha$. Nevertheless, we can also observe dramatic changes of behavior of the blue plots in the third column of Table 2. Indeed, for the first and third curves the quantization error is almost constant when $\alpha = \frac{1}{2}$. Therefore, at some point, the quantization error overrides the discretization error and the estimator fails to converge. Observe that in these special cases, both errors have opposite signs when their magnitudes coincide, thus temporarily collapsing the total error.

<table><caption>**Table 3:** Absolute slopes of the linear models in the log-log plots.</caption><thead><tr><th rowspan="2"></th><th colspan="4">Discretization error</th><th colspan="4">Quantization error</th></tr><tr><th>α = 1/4</th><th>α = 1/3</th><th>α = 2/5</th><th>α = 1/2</th><th>α = 1/4</th><th>α = 1/3</th><th>α = 2/5</th><th>α = 1/2</th></tr></thead><tbody><tr><th>Cubic</th><td>0.26</td><td>0.34</td><td>0.41</td><td>0.51</td><td>0.79</td><td>0.73</td><td>0.48</td><td>0.01</td></tr><tr><th>Spiral</th><td>0.25</td><td>0.34</td><td>0.40</td><td>0.50</td><td>0.75</td><td>0.71</td><td>0.61</td><td>0.48</td></tr><tr><th>Sinusoid</th><td>0.12</td><td>0.16</td><td>0.20</td><td>0.24</td><td>0.67</td><td>0.54</td><td>0.44</td><td>0.08</td></tr></tbody></table>

# 7 Conclusion

In this paper, we propose a convergent turn estimator for simple curves. This so called *naive estimator* (because of its simplicity) rely on polygonal lines $\epsilon$-closed to linear interpolations of the curve. The convergence is ensured provided the edge lengths of the $\epsilon$-approximations tend sufficiently slowly toward 0 as $\epsilon \to 0$. More specifically the edge lengths have to be in $\Omega(\epsilon^{1/2})$. Such $\epsilon$-approximations may be obtained from the digitization process, in particular through Gauss digitizations on cubic grids. In the
<figure><img src="image_15.png" /><figcaption>**Fig. 14:** A wrong polygonal approximation from a Gauss digitization. (a) Original shape. (b) Gauss digitization process on a (2ε) wide grid. (c) Digital shape (in red). (d) Cubic reconstruction. (e-f) Wrong ε-linear approximation of the shape boundary: there is no linear interpolation ε-closed to the green polygon.</figcaption></figure>

latter case, we would say that the naive turn estimator is “multigrid convergent”. Nevertheless, it should be paid attention to the fact that we do not address the problem of finding ε-approximations from digitizations. This issue is not easy and often overlooked. Indeed the digitization process yields an unordered finite set of digital points. Building a correct digital chain from this set, that is a digital polygonal line whose vertices are closed to a chain of the original shape boundary may prove impossible without assumptions on the shape (see Figure 14). This was a motivation for the definitions of par-regularity and turn local boundedness (see Table 1 for definitions and references). The curve simpleness assumption of our result is therefore somewhat misleading in the sense that it does not take into account the hypotheses necessary to obtain those ε-approximations.

With supplementary assumptions, our paper gives lower bounds on the convergence speeds of the naive estimators. Regarding convex plane curves, assuming their ends are strongly Lipschitz, that is of class $C^{1,1}$, $\epsilon$-approximations with edges in $\Theta(\epsilon^{1/2})$ ensure a convergence speed of order $1/2$. With curves that are assumed to be finite concatenations of convex arcs, the edges of the polygonal lines have to be longer, in $\Theta(\epsilon^{1/3})$, to get the best speed of convergence which is $\epsilon^{1/3}$. With sinusoidal curves $x \mapsto x^\eta \sin(\pi/x)$ having infinitely many inflection points, the best convergence speed goes down to $O(\epsilon^{1/5})$ using edges in $\Theta(\epsilon^{2/5})$.

As said in the article introduction, in the future we would like to test the differential curvature estimation by mean of total curvature and length estimations. It is remarkable that the results presented in [14] for differential curvature estimation of $C^3$ boundaries having positive reach coincide with our own results about total curvature estimation on finite concatenation of convex arcs. Indeed, in both cases, the better convergence speed lower bound is $O(\epsilon^{1/3})$, obtained taking an estimator parameter
itself in $O(\epsilon^{1/3})$ (the parameter is the radius of the estimation window for the differential curvature and the edge length for the total curvature). We will also have to extend the curve decomposition in plane convex arcs (here written $C_{\sim}^{P_\epsilon}$) to $nD$ curve chunks on which the collinear configuration cannot occurs. Besides, some more theoretical questions about the turn Lipschitz continuity are worth to be explored. It is easy to build a spiral curve of Lipschitz (with respect to the geodesic distance) and infinite turn which is either unbounded or non closed. But, can we find a compact curve of Lipschitz and infinite turn? If not, is the Lipschitz continuity equivalent to the strongly Lipschitz continuity in the case of compact curves? Equivalently, does the Lipschitz continuity implies the local boundedness of the turn (though neither the parameter of the former property nor the parameter of the latter one can be inferred from the other as shown by Figure A1)? The link with the reach in $nD$, $n \ge 3$, as also to be further investigated.

**Acknowledgments.** We would like to thank É. Le Quentrec and É. Baudrier for their pertinent remarks on an early version of this paper.

We also warmly thank the anonymous reviewers who contributed to greatly improving the quality of this paper.

# Appendix A Curves with strongly Lipschitz turns

The notion of strong Lipschitz turn proposed in this article —that is, Lipschitz continuity of the turn with respect to the Euclidean distance— originates from E. Le Quentrec's thesis. Two properties of the turn were introduced into his article [31] in order to then handle length estimation [10], local boundedness and Lipschitz continuity (with respect to the arc length).

* A curve $C$ in $E^n$ has a locally bounded turn if there exists a positive real $\delta$ such that for any pair of points $a, b \in |C|$ at Euclidean distance from each other less than $\delta$, the turn of the arc of $C$ between $a$ and $b$ is at most $\pi/2$.

* A curve $C$ has a Lipschitz turn if there exists a positive real $k$ such that, for any arc of $C$, the ratio between the turn and the length of the arc is at most $k$. When the curve is the boundary of a compact domain of $E^2$, the local boundedness can be seen as a control over the thickness of this domain whereas the Lipschitz continuity controls the local curvature of the boundary (see Figure A1).

In this appendix, we show that the strong Lipschitz property is equivalent to the set of two turn properties introduced by Le Quentrec et al.

**Proposition 19.** A simple curve in $E^n$ has a strongly Lipschitz turn if and only if this curve has a Lipschitz and locally bounded turn.

*Proof.* In this proof, we denote the length of a curve $X$ by $\mathcal{L}(X)$.

Let $C$ be a curve in $E^n$ having a $k$-strongly Lipschitz turn: $\kappa(C_a^b) \le k\|a-b\|$ for any $a, b \in |C|$. On the one hand, since $\|a-b\| \le \mathcal{L}(C_a^b)$ for any points $a, b \in C$, we directly have that the turn of $C$ is Lipschitz. On the other hand, for any points $a, b \in |C|$ such that $\|a-b\| < \pi/(2k)$, we have $\kappa(C_a^b) \le \pi/2$. Thus, the turn of $C$ is locally bounded.
<figure><img src="image_16.png" /><figcaption>**Fig. A1:** [32, Figure 4] This simple closed curve $F_{r,\epsilon}$ is composed of six half-circles with radius $r$ (in blue) and two line segments with length $2r + \epsilon$ (in red) where $r$ and $\epsilon$ are any positive reals. The turn of the curve $F_{r,\epsilon}$ is $(1/r)$-Lipschitz and $\delta$-locally bounded where $\delta = \min(\epsilon, \sqrt{2}r)$.</figcaption></figure>

Conversely, assume that the turn of $C$ is $k$-Lipschitz and $\delta$-locally bounded. Since the turn of $C$ is locally bounded, the length of $C$ is finite<fnref n="6" /> [31].

Then, given two points $a, b \in |C|$ such that $\|a - b\| \ge \delta$, one has

$$ \kappa(C_a^b) \le k\mathcal{L}(C_a^b) \le k\frac{\mathcal{L}(C)}{\delta}\|a-b\|. \quad (A1) $$

If $\|a - b\| < \delta$, by the locally boundedness assumption, the turn of $C_a^b$ is at most $\pi/2$. Then according to [9, Theo. 5.8.1, p. 151], $\mathcal{L}(C_a^b) \cos(\pi/4) \le \|a - b\|$. Hence, because the turn of $C$ is $k$-Lipschitz,

$$ \kappa(C_a^b) \le k\mathcal{L}(C_a^b) \le k\sqrt{2}\|a-b\|. \quad (A2) $$

Eventually, putting $k' = k \max(\mathcal{L}(C)/\delta, \sqrt{2})$, we derive from Equations (A1) and (A2) that

$$ \kappa(C_a^b) \le k'\|a-b\|. $$

We have proved that the turn of $C$ is $k'$-strongly Lipschitz. □

# Appendix B The curves of strongly Lipschitz turn are the curves which admit a $C^{1,1}$ regular parametrization

Recall that a function $f: \mathbb{R} \to E^n$ belongs to the class $C^{1,1}$ if $f$ is $C^1$ and its derivative is Lipschitz continuous on any compact interval. We show that the simple curves with $C^{1,1}$ regular parametrizations are the curves whose turn is Lipschitz with respect to the Euclidean distance.

**Proposition 20.** A simple curve in $E^n$ has a strongly Lipschitz turn if and only if it admits a $C^{1,1}$ regular parametrization.

<footnote n="6">⁶As a matter of fact, in [31], this property is shown for Jordan curves. The proof relying on the compactness of the curve, it is also applicable here.</footnote>
Proof. Let $\mathcal{C}$ be a curve in $E^n$ whose turn is strongly Lipschitz. From Proposition 19, we derive that $\mathcal{C}$ has a locally bounded turn. Then, according to [31, Corollary 4], the curve $\mathcal{C}$ has a finite turn and is rectifiable. Thanks to [9, Theorems 2.1.4, 3.3.3, 5.1.2], we get that $\mathcal{C}$ has an arc length parametrisation, $\gamma: [0, L] \to E^n$ (where L is the length of $\mathcal{C}$) which has everywhere left and right derivative. Furthermore, by [9, Theorems 5.1.3], given a chain $(x, y, z)$ of $\mathcal{C}$,

$$ \kappa(\mathcal{C}_x^z) = \kappa(\mathcal{C}_x^y) + \kappa(\mathcal{C}_y^z) + \angle(\mathbf{t}_l, \mathbf{t}_r) $$

where $\mathbf{t}_l$ and $\mathbf{t}_r$ are the left and right unit tangent vectors to $\mathcal{C}$ at $y$. Then, the strongly Lipschitz assumption implies that $\angle(\mathbf{t}_l, \mathbf{t}_r) = 0$. In other words, $\gamma$ is differentiable. Let $s_1, s_2 \in [0, L]$ and $\mathbf{t}_1 = \gamma'(s_1), \mathbf{t}_2 = \gamma'(s_2)$. Putting $a_1 = \gamma(s_1)$ and $a_2 = \gamma(s_2)$, we have,

$$ \|\mathbf{t}_1 - \mathbf{t}_2\| \le \angle(\mathbf{t}_1, \mathbf{t}_2) \le \angle(\mathbf{t}_1, a_1\vec{a}_2) + \angle(a_1\vec{a}_2, \mathbf{t}_2). $$

Thanks to Lemma 6, we derive that

$$ \|\mathbf{t}_1 - \mathbf{t}_2\| \le \kappa(\mathcal{C}_{a_1}^{a_2}), $$

and, since $\kappa$ is Lipschitz with respect to the Euclidean distance —thus a fortiori with respect to the geodesic distance,

$$ \|\mathbf{t}_1 - \mathbf{t}_2\| \le k|s_1 - s_2|. $$

Therefore, $\gamma$ is $C^{1,1}$.

Conversely, we now assume that the curve $\mathcal{C}$ admits a $C^{1,1}$ regular parametrization. Then, $\mathcal{C}$ is rectifiable and the parametrisation by arc length of $\mathcal{C}$, $\gamma: [0, L] \to |\mathcal{C}|$ is also a $C^{1,1}$ regular parametrization. Let $s_1, s_2$ be two reals such that $0 \le s_1 < s_2 \le L$ and set $a_1 = \gamma(s_1)$ and $a_2 = \gamma(s_2)$. By [9, Theorem 5.2.2], the turn of $\mathcal{C}_{a_1}^{a_2}$ is equal to the length of the tangent indicatrix of $\mathcal{C}_{a_1}^{a_2}$, that is, to the total variation of the derivative $\gamma'$ between $s_1$ and $s_2$. Let $k$ be the Lipschitz parameter of $\gamma'$ and $\gamma_0$ be the parametrisation by arc length of a circle with radius $r = 1/k$. Since $\gamma'$ is $k$-Lipschitz, the total variation of $\gamma'$ between $s_1$ and $s_2$ is upper bounded by $|s_1 - s_2|/r$, which is the turn of the arc $\gamma_0([s_1, s_2])$. Hence,

$$ \kappa(\mathcal{C}_{a_1}^{a_2}) \le \kappa(\gamma_0([s_1, s_2))). \quad (B3) $$

This last result being valid for any interval $[s_1, s_2] \subset [0, L]$, the hypotheses of Schur's Comparison Theorem [40] are fulfilled. Thus,

$$ \|\gamma_0(s_1) - \gamma_0(s_2)\| \le \|\gamma(s_1) - \gamma(s_2)\|. \quad (B4) $$

Let us now assume that the turn of $\gamma_0([s_1, s_2])$ is at most $\pi$, that is $|s_1 - s_2| \le r\pi$. Then, this turn is linked to the chord of $\gamma_0([s_1, s_2])$ by

$$ \|\gamma_0(s_1) - \gamma_0(s_2)\| = 2r \sin \left( \frac{\kappa(\gamma_0([s_1, s_2]))}{2} \right). $$
Hence, for the sine function is concave on $[0, \frac{\pi}{2}]$,

$$ \|\gamma_0(s_1) - \gamma_0(s_2)\| \geq \frac{2r}{\pi} \kappa(\gamma_0([s_1, s_2))). \quad (B5) $$

Putting Equations (B3), (B4), (B5) together, we obtain

$$ \forall s_1, s_2 \in [0, L], |s_1 - s_2| \leq r\pi \implies \kappa(C_{\gamma(s_2)}^{\gamma(s_2)}) \leq \frac{k\pi}{2} \|\gamma(s_1) - \gamma(s_2)\|. \quad (B6) $$

We now examine the case $|s_1 - s_2| > r\pi$. For any $s \in [0, L]$, we set $I_s = [0, L] \setminus (s - r\pi, s + r\pi)$, $C_s = \gamma(I_s)$ and $\delta(s) = d(\gamma(s), C_s)$ where $d(\cdot, \cdot)$ denotes the Euclidean distance. Since $C_s$ is a compact set and $C$ is simple, $\delta(s)$ is a positive real for any $s$. Let us show that $\delta$ has a positive infimum on $[0, L]$. Since the curve $C$ need not be close, the map $\delta: [0, L] \to [0, +\infty)$ may have two points of discontinuity. Then, we have to split the proof into three parts.

Firstly, let us prove that the map $\delta$ is continuous on $[r\pi, L - r\pi]$. For any $s \in [r\pi, L - r\pi]$, $I_s$ is the union of two non empty intervals, $[0, s - r\pi]$ and $[s + r\pi, L]$. We have, for any $s, s_0$ in $[r\pi, L - r\pi]$,

$$ d(\gamma(s), C_s) \leq d(\gamma(s), \gamma(s_0)) + d(\gamma(s_0), C_{s_0}) + d_H(C_{s_0}, C_s), $$

where $d_H$ denotes the Hausdorff distance. Hence,

$$ |\delta(s) - \delta(s_0)| \leq d(\gamma(s), \gamma(s_0)) + d_H(C_{s_0}, C_s). $$

Since $\gamma$ is uniformly continuous on $[0, L]$, sufficiently small differences $s - s_0$ yield $d(\gamma(s), \gamma(s_0)) < \epsilon$ and $d_H(C_{s_0}, C_s) < \epsilon$ for any given $\epsilon$. Thereby, we have proved that $\delta$ is continuous on $[r\pi, L - r\pi]$. Let $s_0 \in [r\pi, L - r\pi]$ such that $\delta_0 = \delta(s_0)$ is the minimum value of $\delta$ on the compact set $[r\pi, L - r\pi]$. Then, $\delta_0 = d(\gamma(s_0), \gamma(t_0))$ for some $t_0$ in $I_{s_0}$. Because $C$ is simple, we have $\delta_0 > 0$.

To obtain a similar result on the left part $[0, r\pi]$ of the interval $[0, L]$, we need to slightly modify the definition of $I_s$. Now, we put $I_s = [0, L] \setminus [s - r\pi, s + r\pi)$. Hence, $I_s = [s + r\pi, L]$ for any $s \in [0, r\pi]$. This definition coincide with the former one except when $s = r\pi$ where we would have had $I_{r\pi} = \{0\} \cup [2r\pi, L]$. Notably, this implies that both meanings of $\delta$ coincide on $[0, r\pi)$. The rest of the reasoning is identical as before: with this modification, $\delta_s$ is continuous on $[0, r\pi]$ and we find a positive real $\delta_1$ such that $\delta \geq \delta_1$ on $[0, r\pi]$. In particular, $\delta \geq \delta_1$ on $[0, r\pi)$ with the first acceptance of $\delta$. Alike, we find positive real $\delta_2$ such that $\delta \geq \delta_2$ on $(L - r\pi, L]$.

Eventually, we have found a positive real $\delta_3 = \min(\delta_0, \delta_1, \delta_2)$ such that $d(\gamma(s), \gamma([0, L] \setminus (s - r\pi, s + r\pi))) \geq \delta_3$ for any $s \in [0, L]$. We end the proof by putting $k_2 = \kappa(C)/\delta_3$ which is finite since $C$ is $C^{1,1}$ ([9, Theorem 5.4.3]). Let $s_1, s_2$ in $[0, L]$ such that $|s_1 - s_2| > r\pi$. We have

$$ \kappa(C_{\gamma(s_2)}^{\gamma(s_2)}) \leq \kappa(C) \leq \frac{\kappa(C)}{\delta_3} \delta(s_1) \leq \frac{\kappa(C)}{\delta_3} \|\gamma(s_1) - \gamma(s_2)\|. \quad (B7) $$
In view of Formulas (B6) and (B7), we conclude that the turn of $\mathcal{C}$ is strongly Lipschitz with parameter $\max(k\pi/2, \kappa(\mathcal{C})/\delta_3)$. $\square$

## References

[1] Matsumoto, T., Sato, K., Matsuoka, Y., Kato, T.: Quantification of “complexity” in curved surface shape using total absolute curvature. Computers & Graphics **78**, 108–115 (2019) https://doi.org/10.1016/j.cag.2018.10.009

[2] Ujiie, Y., Kato, T., Sato, K., Matsuoka, Y.: Curvature entropy for curved profile generation. Entropy **14**(3), 533–558 (2012) https://doi.org/10.3390/e14030533

[3] Goldlücke, B., Cremers, D.: Introducing total curvature for image processing. In: Metaxas, D.N., Quan, L., Sanfeliu, A., Gool, L.V. (eds.) IEEE International Conference on Computer Vision, ICCV 2011, Barcelona, Spain, November 6-13, 2011, pp. 1267–1274. IEEE Computer Society, Washington (2011). https://doi.org/10.1109/ICCV.2011.6126378

[4] Olsson, C., Boykov, Y.: Curvature-based regularization for surface approximation. In: 2012 IEEE Conference on Computer Vision and Pattern Recognition, pp. 1576–1583 (2012). https://doi.org/10.1109/CVPR.2012.6247849

[5] Moreno, R., Wang, C., Smedby, Ö.: Vessel wall segmentation using implicit models and total curvature penalizers. In: Kämäräinen, J., Koskela, M. (eds.) Image Analysis, 18th Scandinavian Conference, SCIA 2013, Espoo, Finland, June 17-20, 2013. Proceedings. Lecture Notes in Computer Science, vol. 7944, pp. 299–308. Springer, Berlin (2013). https://doi.org/10.1007/978-3-642-38886-6\_29

[6] Olsson, C., Ulén, J., Boykov, Y., Kolmogorov, V.: Partial enumeration and curvature regularization. In: 2013 IEEE International Conference on Computer Vision, pp. 2936–2943 (2013). https://doi.org/10.1109/ICCV.2013.365

[7] Kishimoto, K.: Characterizing digital convexity and straightness in terms of “length” and “total absolute curvature”. Computer vision and image understanding **63**(2), 326–333 (1996) https://doi.org/10.1006/cviu.1996.0022

[8] Fenchel, W.: Über krümmung und windung geschlossener raumkurven. Mathe-matische Annalen **101**(1), 238–252 (1929) https://doi.org/10.1007/bf01454836

[9] Alexandrov, A.D., Reshetnyak, Y.G.: General Theory of Irregular Curves. Kluwer Academic Publishers, Alphen aan den Rijn (1989). https://doi.org/10.1007/978-94-009-2591-5

[10] Le Quentrec, É., Mazo, L., Baudrier, É., Tajine, M.: Monotonic Sampling of a Continuous Closed Curve with Respect to Its Gauss Digitization: Application to Length Estimation. Journal of Mathematical Imaging and Vision **64**(8), 869–891 (2022) https://doi.org/10.1007/s10851-022-01098-8
[11] Cohen-Steiner, D., Edelsbrunner, H.: Inequalities for the curvature of curves and surfaces. Found. Comput. Math. **7**(4), 391–404 (2007) https://doi.org/10.1007/s10208-005-0200-3

[12] Lin, W.-Y., Chiu, Y.-L., Widder, K., Hu, Y., Boston, N.: Robust and accurate curvature estimation using adaptive line integrals. EURASIP Journal on Advances in Signal Processing **2010**, 1–14 (2010) https://doi.org/10.1155/2010/240309

[13] Lachaud, J.-O.: Multigrid-convergence of digital curvature estimators. Actes des rencontres du CIRM, vol. 3, pp. 171–181. CEDRAM, Grenoble (2014). https://doi.org/10.5802/acirm.66

[14] Lachaud, J.-O., Coeurjolly, D., Levallois, J.: Robust and convergent curvature and normal estimators with digital integral invariants. Modern Approaches to Discrete Curvature, 293–348 (2017) https://doi.org/10.1007/978-3-319-58002-9_9

[15] Milnor, J.W.: On the Total Curvature of Knots. The Annals of Mathematics **52**(2), 248 (1950) https://doi.org/10.2307/1969467

[16] Sullivan, J.M.: Curves of finite total curvature. In: Discrete Differential Geometry, pp. 137–161. Birkhäuser, Basel (2008). https://doi.org/10.1007/978-3-7643-8621-4_7

[17] Latecki, L.J., Rosenfeld, A.: Supportedness and tameness differentialless geometry of plane curves. Pattern Recognition **31**(5), 607–622 (1998) https://doi.org/10.1016/s0031-3203(97)00071-x

[18] Coeurjolly, D., Lachaud, J., Levallois, J.: Integral based curvature estimators in digital geometry. In: González-Díaz, R., Jiménez, M.J., Medrano, B. (eds.) Discrete Geometry for Computer Imagery - 17th IAPR International Conference, DGCI 2013, Seville, Spain, March 20-22, 2013. Proceedings. Lecture Notes in Computer Science, vol. 7749, pp. 215–227. Springer, Berlin (2013). https://doi.org/10.1007/978-3-642-37067-0_19

[19] Roussillon, T., Lachaud, J.: Accurate curvature estimation along digital contours with maximal digital circular arcs. In: Aggarwal, J.K., Barneva, R.P., Brimkov, V.E., Koroutchev, K., Korutcheva, E. (eds.) Combinatorial Image Analysis - 14th International Workshop, IWCIA 2011, Madrid, Spain, May 23-25, 2011. Proceedings. Lecture Notes in Computer Science, vol. 6636, pp. 43–55. Springer, Berlin (2011). https://doi.org/10.1007/978-3-642-21073-0_7

[20] Coeurjolly, D., Lachaud, J.-O., Roussillon, T.: Multigrid convergence of discrete geometric estimators. In: Brimkov, V., Barneva, R. (eds.) Digital Geometry Algorithms, Theoretical Foundations and Applications of Computational Imaging. Lecture Notes in Computational Vision and Biomechanics, vol. 2, pp. 395–424. Springer, Berlin (2012). https://doi.org/10.1007/978-94-007-4174-4_13
[21] Schindele, A., Massopust, P., Forster, B.: Multigrid convergence for the MDCA curvature estimator. J. Math. Imaging Vis. **57**(3), 423–438 (2017) https://doi.org/10.1007/s10851-016-0685-1

[22] Pottmann, H., Wallner, J., Huang, Q.-X., Yang, Y.-L.: Integral invariants for robust geometry processing. Computer Aided Geometric Design **26**(1), 37–60 (2009) https://doi.org/10.1016/j.cagd.2008.01.002

[23] Coeurjolly, D., Lachaud, J., Levallois, J.: Multigrid convergent principal curvature estimators in digital geometry. Comput. Vis. Image Underst. **129**, 27–41 (2014) https://doi.org/10.1016/j.cviu.2014.04.013

[24] Cazals, F., Chazal, F., Lewiner, T.: Molecular shape analysis based upon the morse-smale complex and the connolly function. In: Fortune, S. (ed.) Proceedings of the 19th ACM Symposium on Computational Geometry, San Diego, CA, USA, June 8-10, 2003, pp. 351–360. ACM, New York (2003). https://doi.org/10.1145/77792.777845

[25] Federer, H.: Curvature measures. Transactions of the American Mathematical Society **93**(3), 418–491 (1959) https://doi.org/10.1090/s0002-9947-1959-0110078-1

[26] Serra, J.: Image Analysis and Mathematical Morphology vol. 1. Academic press, London (1982)

[27] Pavlidis, T.: Algorithms for Graphics and Image Processing. Springer, Berlin, Heidelberg (1982). https://doi.org/10.1007/978-3-642-93208-3

[28] Gross, A., Latecki, L.: Digitizations preserving topological and differential geometric properties. Computer Vision and Image Understanding **62**(3), 370–381 (1995) https://doi.org/10.1006/cviu.1995.1061

[29] Latecki, L.J., Conrad, C.b., Gross, A.: Preserving topology by a digitization process. Journal of Mathematical Imaging and Vision **8**(2), 131–159 (1998) https://doi.org/10.1023/A:1008273227913

[30] Lachaud, J., Thibert, B.: Properties of gauss digitized shapes and digital surface integration. J. Math. Imaging Vis. **54**(2), 162–180 (2016) https://doi.org/10.1007/s10851-015-0595-7

[31] Le Quentrec, É., Mazo, L., Baudrier, É., Tajine, M.: Local Turn-Boundedness, a curvature control for continuous curves with application to digitization. Journal of Mathematical Imaging and Vision **62**, 673–692 (2020) https://doi.org/10.1007/s10851-020-00952-x

[32] Le Quentrec, É., Mazo, L., Baudrier, É., Tajine, M.: LTB curves with Lipschitz turn are par-regular. Technical report, Laboratoire ICube, université de
Strasbourg (December 2021). https://hal.archives-ouvertes.fr/hal-03480735

[33] Peano, G.: Sur une courbe, qui remplit tout une aire plane. In: Mathematische Annalen vol. 36, pp. 157–160. Teubner, Berlin (1890). https://doi.org/10.1007/bf01199438

[34] Niculescu, C., Persson, L.-E.: Convex Functions and Their Applications vol. 23. Springer, Berlin (2006). https://doi.org/10.1007/0-387-31077-0

[35] Koch, H.: Une méthode géométrique élémentaire pour l'étude de certaines questions de la théorie des courbes planes. Acta Mathematica 30(none), 145–174 (1906) https://doi.org/10.1007/BF02418570

[36] Chern, S.-S.: Curves and surfaces in Euclidean space. In: Global Differential Geometry. Studies in Mathematics, vol. 27. The Mathematical Association of America, Washington (1989)

[37] Castano, D., Paksoy, V.E., Zhang, F.: Angles, triangle inequalities, correlation matrices and metric-preserving and subadditive functions. Linear Algebra and its Applications 491, 15–29 (2016) https://doi.org/10.1016/j.laa.2014.10.011 . Proceedings of the 19th ILAS Conference, Seoul, South Korea 2014

[38] Wikipedia contributors: Big O notation — Wikipedia, The Free Encyclopedia (2024). https://en.wikipedia.org/wiki/Big-O_notation#The_Knuth_definition

[39] Mazo, L., Baudrier, É.: Non-local length estimators and concave functions. Theor. Comput. Sci. 690, 73–90 (2017) https://doi.org/10.1016/J.TCS.2017.06.005

[40] Schur, A.: Über die schwarzsche extremaleigenschaft des kreises unter den kurven konstanter krümmung. Mathematische Annalen 83(1), 143–148 (1921) https://doi.org/10.1007/bf01464234