Locally Turn-Bounded Curves Are Quasi-Regular

Abstract

The characteristics of a digitization of a Euclidean planar shape depends on the digitization process but also on the shape border regularity. The notion of Local Turn Boundedness (LTB) was introduced by the authors in Le Quentrec, É. et al.: Local Turn-Boundedness: A curvature control for a good digitization, DGCI 2019 so as to have multigrid convergent perimeter estimation on Euclidean shapes. If it was proved that the par-regular curves are locally turn bounded, the relation with the quasi-regularity introduced in Ngo, P.et al.: Convexity-Preserving Rigid Motions of 2D Digital Objects, DGCI 2017 had not yet been explored. Our paper is dedicated to prove that for planar shapes, local turn-boundedness implies quasi-regularity.

1 Introduction

A loss of information is inherent to any digitization of a continuous shape. The control of the shape border can allow the digitization to inherit of continuous shape properties. Thus the notion of local-turn boundedness (LTB) introduced in [6] by the authors makes it possible to preserve the shape connectivity and well-composedness for a Gauss digitization under a condition on the grid step. The class of LTB curves is not the first attempt to control the shape border for digitization. One can cite the par-regularity [12] and its generalizations including shapes with spikes: half-regularity [13], r-stability [9], quasi(r)-regularity [10] and the $\mu$-reach [2]. There are links among the existing notions and also with the LTB notion. The following equivalences have already been shown: in [3], the equivalence between the class $C^{1,1}$ (curves with Lipschitz unit tangents) and the par-regular class; in [4], the equivalence between par-regular class and the class of curves with a positive reach; in [7, 8], the equivalence between the class of curves with a positive reach and LTB curves with Lipschitz turn.

This paper is dedicated to show that LTB implies the quasi-regularity. The proof is composed of several but necessary steps. The key point of the proof is the connectivity of the eroded of a LTB shape. It consists in showing that close points, or on the contrary distant points, in the eroded set can be joined by a path inside the shape. The main difficulty is to define precisely the terms “close” and “far” to cover all the point distances in the eroded set while making proof possible.

In Sect. 2, the main notions and some useful properties –some of them revisited– are recalled. Section 3 gives all the steps to prove the implication. The conclusion and some perspectives are given in Sect. 4.

2 Definitions

Notations. The complementary of a subset S of $\mathbb R^2$ is noted $S^c$. We write $\bar{A}$ for the topological closure of a set A and $\partial A$ for its topological boundary. We note B(c, r) the open disk centered in c and of radius r. The notation $[x_i]_{i=0}^{N}$ designates the polygonal line whose ordered sequence of vertices is $(x_i)_{i=0}^{N}$. When $x_0= x_N$, the polygonal line is actually a polygon. The geometric angle between two vectors $\vec u$ and $\vec v$, or between two directed straight lines oriented by $\vec u$ and $\vec v$, is denoted by $\angle (\vec u , \vec v)$. It is the absolute value of the reference angle taken in $(-\pi ,\pi ]$ between the two vectors. Given three points x, y, z, we also write $\widehat{xyz}$ for the geometric angle between the vectors $x-y$ and $z-y$. We write $\mathcal C_{a,b}$ for an arc of a curve $\mathcal C$ between the points a and b.

The two following definitions introduce the notion of local turn boundedness.

Definition 1

(Turn, [1]).

• The turn $\kappa (L)$ of a polygonal line $L=[x_i]_{i=0}^{N}$ is defined by:

  $$\begin{aligned} \kappa (L):=\sum _{i=1}^{N-1}\angle (x_i-x_{i-1}, x_{i+1}- x_i). \end{aligned}$$

• The turn $\kappa (P)$ of a polygon $P=[x_i]_{i=0}^{N}$ (where $x_{N}=x_0$ and $x_{N+1}=x_1$) is defined by:

  $$\begin{aligned} \kappa (P):=\sum _{i=1}^{N}{\angle (x_i-x_{i-1}, x_{i+1}- x_i)}. \end{aligned}$$

• The turn $\kappa (\mathcal C)$ of a simple curve $\mathcal C$ (respectively of a Jordan curve) is the supremum of the turn of its inscribed polygonal lines (respectively of its inscribed polygons).

At each point c of a curve whose turn is finite, there exists a left-hand and a right-hand tangent vectors, denoted by $e_l(c)$ and $e_r(c)$ [1].

Property 1

(Fenchel’s Theorem, [1] Theorem 5.1.5). The turn of a Jordan curve is greater than or equal to $2 \pi$. The equality case occurs if and only if the interior of $\mathcal C$ is convex.

Definition 2

(Proposition 2 [7]). A Jordan curve $\mathcal C$ is $(\theta ,\delta )$-LTB if for any two points a and b in $\mathcal C$ such that $\mathrm d(a,b) < \delta$, the turn of one of the arcs of the curve $\mathcal C$ delimited by a and b is less than or equal to $\theta$.

As the $(\theta ,\delta )$-LTB-curve set is growing with $\theta$, the properties established for $\theta =\theta _0$ are also available for $\theta \le \theta _0$. In the rest of the paper, $\theta$ is fixed to $\pi /2$ and we write $\delta$-LTB instead of $(\pi /2, \delta )$-LTB.

Notice that two distinct points of a Jordan curve delimit two arcs of the curve. The notion of straightest arc introduced in [6] makes it possible to distinguish these two arcs.

Property 2

([7], Definition 6 and Proposition 4). Let a, b be two distinct points of a $\delta$-LTB curve $\mathcal C$. If $\mathrm d(a,b) < \delta$, then there exists a unique arc of $\mathcal C$ between a and b whose turn is less than or equal to ${\pi }/{2}$. This arc, denoted by $\mathcal C|_{a}^{b}$, is included in the closed disk with diameter [a, b] and is called the straightest arc between a and b.

Let us quote a recent result which makes easier the use of straightest arcs.

Property 3

([8], Lemma 1). Let a and b two points of a $\delta$-LTB curve such that $\mathrm d(a,b)<\delta$. Let $\mathcal C|_{a}^{b}$ be the straightest arc between a and b. Then,

$$\angle (e_l(a),e_r(a)) + \kappa (\mathcal C|_{a}^{b}) + \angle (e_l(b),e_r(b)) \le \frac{\pi }{2}. $$

The following proposition is a very slight quantitative improvement of [7, Proposition 5]. Nevertheless, this improvement is absolutely necessary to get the main result of this paper.

Proposition 1

Let $\mathcal C$ be a $(\theta , \delta )$-LTB curve and $a\in \mathcal C$. Then, for any $\epsilon < \delta$, the intersection of $\mathcal C$ with the closed disk $\bar{B}(a,\epsilon )$ is path-connected and is therefore an arc of $\mathcal C$. Furthermore, the turn of this arc is less than or equal to $2\theta$.

Proof

The proof is exactly the same as the one given in [7] except that, taking into account Property 3, we can omit the term $\angle \big (e_l(a),e_r(a)\big )$ so as to upper bound the curvature of the arc $\mathcal C\cap B(a,\epsilon )$ by $2\theta$ instead of $3\theta$.   $\square$

We recall here the notions of par-regularity and quasi-regularity.

Definition 3

(par(r)-regularity, [5]). Let $\mathcal C$ be a Jordan curve of interior K.

• A closed disk $\bar{B}(c_i,r)$ is an inside osculating disk of radius r to $\mathcal C$ at point $a \in \mathcal C$ if $\mathcal C\cap \bar{B}(c_i,r)= \{ a\}$ and $\bar{B}(c_i, r) \subset K \cup \{a\}$.

• A closed disk $\bar{B}(c_e,r)$ is an outside osculating disk of radius r to $\mathcal C$ at point $a \in \mathcal C$ if $\mathcal C\cap \bar{B}(c_e,r)= \{ a\}$ and $\bar{B}(c_e, r) \subset \mathbb R^2 \setminus (\mathcal C\cup K) \cup \{a\}$.

• A curve $\mathcal C$ or a set K is par(r)-regular if there exist inside and outside osculating disks of radius r at each $a \in \mathcal C$.

As noticed in [11], for a bounded simply connected set S, the above definition can be rephrased in the following way¹:

The set S is par(r)-regular if and only if

• $S \ominus \bar{B}(0,r)$ is non-empty and connected,

• $S^c \ominus \bar{B}(0,r)$ is connected,

• $S =(S \ominus \bar{B}(0,r)) \oplus \bar{B}(0,r)$ ,

• $S^c =(S^c \ominus \bar{B}(0,r)) \oplus \bar{B}(0,r)$,

with $\oplus$, $\ominus$ the standard dilation and erosion operators.

In order to consider shapes with angles, the two last items of par-regularity are relaxed in Definition 4 allowing the border of the shape to oscillate in a margin around its opening.

Definition 4

(Quasi-regularity [10, 11] ). Let $S \subset \mathbb R^n$ ($n=2,3$) be a bounded, simply connected set. We say that S is quasi-r -regular with margin $r'-r$ (with $0<r \le r'$) if it satisfies the following four properties

• $S \ominus \bar{B}(0,r)$ is non-empty and connected,

• $S^c \ominus \bar{B}(0,r)$ is connected,

• $S \subset S \ominus \bar{B}(0,r) \oplus \bar{B}(0,r')$,

• $S^c \subset S^c \ominus \bar{B}(0,r) \oplus \bar{B}(0,r')$.

3 Main Result

For sake of readability of the article, we state the main result—Theorem 1—before the propositions and lemmas needed for the proof.

Theorem 1

Let S be a compact subset of the plane $\mathbb R^2$ whose boundary is $\delta$-LTB. Then S is quasi-r-regular with margin $(\sqrt{2} -1) r$ for any $r<{\delta }/{\sqrt{10+4\sqrt{2}}}$.

Our first intermediate result is an improvement of a proposition about turn originally stated in [7] that roughly asserts that avoiding a convex obstacle bounds from below the turn of a curve. It was stated for convex polygonal obstacles in [7, Lemma 3] and for convex obstacles in a particular configuration in [8, Lemma 10]. The new version presented below is valid in a more general configuration (see Fig. 1).

Proposition 2

Let $\mathcal C$ be a simple curve with endpoints a, b. Let $H_{a,b}$ be a half-plane having a and b in its boundary and S be a closed set included in the closure of a bounded connected component of $\mathbb R^2\setminus (\mathcal C\cup [a,b])$ and whose intersection with the half-plan $H_{a,b}$ is not included in the line passing through a and b. Then,

$$\kappa (\mathcal C) \ge \kappa ( \partial {\text {conv}}(H_{a,b}\cap S\cup [a,b]) \setminus (a,b) ),$$

where $\partial {\text {conv}}(\cdot )$ stands for the boundary of the convex hull.

Fig. 1.

Proposition 2 states that the blue curve with endpoints a and b has a turn greater than the red curve $\partial {\text {conv}}(H_{a,b}\cap S\cup [a,b]) \setminus (a,b)$ where $H_{a,b}$ is the grey half-plane.

Proof

We begin the proof by stating and proving some facts about convex polygons. So, let $n\ge 3$ and $P=[a_i]_{i=0}^n$ with $a_n=a_0$ be a convex polygon. Then,

• Claim 1. Let $\sigma$ be a permutation of [1, n] such that $\sigma (1)=1$ and $\sigma (n)=n$. Then, $\kappa ([a_{\sigma (i)}]_{i=1}^n) \ge \kappa ([a_i]_{i=1}^n)$.

• Claim 2. Let [a, b, c, d, a] be a convex polygon of $\mathbb R^2$. For any point $b'$ on the half-line $\overrightarrow{\mathrm{c,b}}\setminus [c,b)$, for any point $c'$ on the half-line $\overrightarrow{\mathrm{a,c}}\setminus [a,c)$ and for any point $b''$ on the half-line $\overrightarrow{\mathrm{d,b}}\setminus [d,b)$, the polygons $[a,b',c,a]$ and $[a,b'',c',d,a]$ are convex and the turn of the polygonal lines $[a,b',c]$ and $[a,b'',c',d]$ are respectively greater than or equal to the turn of the polygonal lines [a, b, c] and [a, b, c, d]. Claim 2 is also valid in the degenerate case where b, a, d, c are aligned in this order.

Proof of Claim 1: The turn of the polygonal line $Q=[a_{\sigma (i)}]_{i=1}^n$ is the sum of the turns at each vertex $a_{\sigma (i)}$, $2\le i\le n-1$. Since P is convex, the turn of Q at $a_{\sigma (i)}$ is bounded from below by the turn of the polyline $[a_{\sigma (i)-1}, a_{\sigma (i)}, a_{\sigma (i)+1}]$, that is by the turn at $a_{\sigma (i)}$ for the polyline $[a_i]_{i=1}^n$.

Proof of Claim 2: The triangle $[a, b', c, a]$ is obviously convex. The interior angle of $[a, b'', c,' ,d ,a]$ at $b''$ is maximum when $b''= b$ and $c'$ at infinity. Thereby, it is never a reflex angle. Alike, the angle at $c'$ is never reflex and the quadrilateral $[a,b'', c,' ,d ,a]$ is convex. Furthermore, the turn of the polygons $[a, b', c, a]$, $[a,b'', c,' ,d ,a]$ , [a, b, c] and [a, b, c, d] are equal to $2\pi$ by Property 1 and, by definition of $b'$, $c'$ and $b''$, the interior angles at a and c for $[a, b', c, a]$ (resp. a and d for $[a,b'', c,' ,d ,a]$) are greater than or equal to those for [a, b, c, a] (resp. for [a, b, c, d, a]). We derive that $\kappa ([a,b', c])\ge \kappa ([a,b,c])$ and $\kappa ([a,b'', c', d])\ge \kappa ([a,b,c,d])$. In the degenerate case, the reader can check that the turns of the polygons [a, b, c], [a, b, c, d, a], $[a, b', c, a]$ and $[a,b'', c,' ,d ,a]$ are equal to $2\pi$.

Let us go back to the main proof. Put $T=\partial {\text {conv}}(H_{a,b}\cap S\cup [a,b])$. Observe that T includes the straight segment [a, b] and has a non-empty interior (for $H_{a,b}\cap S$ is not included in the line passing through a and b). Thus, $P=T\setminus (a,b)$ is a curve with endpoints a and b. Firstly, we assume that T is a polygon. Consequently, P is a polygonal line and we denote by c, resp. d the vertex of the edge of P whose other end is a, resp b. Notice that the turns of T and of the quadrilateral (or triangle) [a, c, d, b, a] are equal to $2\pi$ (Property 1). Also, observe that if [a, c, d, b, a] is degenerate, then c, a, b and d are aligned in this order. Thereby, the turn of P and the polyline [a, c, d, b] are equal.

Since the component of $\mathbb R^2\setminus (\mathcal C\cup [a,b])$ whose closing includes S is bounded and $c,d\in S$, any half-line with initial point c or d cuts the curve $\mathcal C\cup [a,b]$. Then, thanks to Claim 2, we define the points $c'$ and $d'$ on $\mathcal C$ such that $[a,c',d',b,a]$ is a convex quadrilateral with vertices on $\mathcal C$. Observe that either the polygonal line $[a,c',d',b]$ or the polygonal line $[a,d',c',b]$ is inscribed in $\mathcal C$. We denote by Q the one which is inscribed in $\mathcal C$ and we set $Q'=[a,c',d',b]$.

We now end the proof in the same manner as in [7, Lemma 3]. We have $\kappa (\mathcal C) \ge \kappa (Q)$ by definition of $\kappa (\mathcal C)$. Moreover, $\kappa (Q)\ge \kappa (Q')$ by Claim 1. Besides, $\kappa (Q') \ge \kappa ([a,c,d,b])$ by Claim 2. Since $\kappa ([a,c,d,b]) = \kappa (P)$, we get $\kappa (\mathcal C)\ge \kappa (P)$. In the general case where P is not polygonal, it suffices to observe that the result is valid for any polygonal line inscribed in P. Then, taking the supremum of the turns of all such polygonal lines, we obtain the desired result.

   $\square$

The statement of the following proposition should be compared with the definition of par-regularity. Indeed, from Definition 3, it is possible to derive that any point lying in the closure S of the interior, or the exterior, of a Jordan par(r)-regular curve is contained in a circle with radius r included in S.

Proposition 3

Let $\mathcal C$ be a $\delta$-LTB curve and S be the closure of either the interior or the exterior of $\mathcal C$. For each point $p\in S$, there exists a square of diameter $\delta$ included in S and containing p.

Proof

The proof is divided in three parts. In the first one, we prove the statement for the points of $\mathcal C$. In the second part, we prove the statement for points in $S\setminus (S\ominus \bar{B}(0,\delta /2))$. The last part treats the obvious case of points in $S\ominus \bar{B}(0,\delta /2)$ and concludes the proof.

• 1. This part of the proof is illustrated by Fig. 2 (center). In a first step, given a point $p\in \mathcal C$, we prove that there exists a circular sector of center p and radius $\frac{\delta }{\sqrt{2}}$ included in S. In the second step, we prove that this circular sector extends to a square in S. We set $\bar{B}_p=\bar{B}(p, \delta /\sqrt{2})$.

  • (a) Let $p\in \mathcal C$. By Proposition 1, the intersection of the curve $\mathcal C$ with any disk included in $\bar{B}_p$ is an arc of $\mathcal C$ (it is connected) and its turn is less than or equal to $\pi$. We set $\mathcal C_{a,b}=\mathcal C\cap \bar{B}_p$. Then, the arc $\mathcal C_{a,b}$ splits the disk $\bar{B}_p$ into three connected components: the arc $\mathcal C_{a,b}$ itself, included in $\mathcal C$, another one included in the interior of S called I and the last one included in the exterior of S. Let A be the circular sector of $\bar{B}_p$ delimited by [a, p, b] including $I\cap \partial \bar{B}_p$. Let $\mathcal C_{a,p}$, resp. $\mathcal C_{b,p}$, be the subarc of $\mathcal C_{a,b}$ from a, resp. b, included to p excluded.

    Let $c_a \in \mathcal C_{a,p}$ and $c_b \in \mathcal C_{b,p}$ and, by contradiction, assume that $\widehat{c_apc_b} < \frac{\pi }{2}$. Then, the distance between $c_a$ and $c_b$ is less than $\delta$. We derive that $\mathcal C|_{c_a}^{c_b}$ exists. Nevertheless, on the one hand, the turn of the arc from $c_a$ to $c_b$ passing through p is greater than or equal to $\kappa ([c_a,p,c_b])$ which is greater than $\pi /2$ (by the contradiction assumption). On the other hand, the turn of the arc from $c_a$ to $c_b$ not passing through p is greater than $\kappa (\mathcal C\setminus \mathcal C_{a,b})$ which is greater than $\pi$ (by Fenchel’s Theorem and the additivity of turns). We get an absurdity. Hence, $\widehat{c_apc_b} \ge \frac{\pi }{2}$ for any $c_a \in \mathcal C_{a,p}$, $c_b \in \mathcal C_{b,p}$. Furthermore, a basic calculation of angles shows that the radius [p, m] which is the angle bisector of $\widehat{apb}$ is not intersected by the arc $\mathcal C_{a,b}$ (see Fig. 2-left).

    Let A be the smallest angular sector of $\partial \bar{B}_p$ containing I. Notice that $A \ne \partial \bar{B}_p$. Let D be the subset of the circular sectors of $\partial \bar{B}_p$ delimited by radii intersecting $\mathcal C_{a,p}$ and $\mathcal C_{b,p}$ and included in A. Since the radius [p, m] is included in all the sectors of D and since any intersection of angular sectors is a sector or empty, the set $\bigcap \{d\mid d\in D\}$ is a circular sector. Put $\varOmega = \bigcap \{d\mid d\in D\} \cap \partial \bar{B}_p$.

    Let $x_0$ and $x_1$ be the ends of the arc of circle $\varOmega$. For any $\epsilon >0$, there exists $x_0', x_1' \in \partial B(p, \frac{\delta }{\sqrt{2}}) \setminus \varOmega$ such that $\widehat{x_0px_0'} <\epsilon$ and $\widehat{x_1px_1'} <\epsilon$. One of the segments $(px_0']$ and $(px_1']$ intersects $\mathcal C_{a,p}$ at a point $c_a'$, and the other intersects $\mathcal C_{b,p}$ at a point $c_b'$. Moreover $\widehat{c_a'p c_b'}\ge \frac{\pi }{2}$, then for any $\epsilon >0$, $\widehat{x_0p x_1}\ge \widehat{x_0'px_1'} -2 \epsilon$. Then the sector $\bigcap \{d\mid d\in D\}$ is included in $I\cap \bar{B}_p$ and has its angle greater than or equal to $\frac{\pi }{2}$.

  • (b) Let Q be a square of side length $\delta /\sqrt{2}$ having p as vertex and two edges included in $A'$. By contradiction, let c be a point of $\mathcal C$ lying in the interior of Q. Then, $\mathrm d(c,p)<\delta$. Thus there exists a straightest arc $\mathcal C|_{c}^{p}$ between c and p. This straightest arc is included in the disk D with diameter [c, p] by Property 2. Besides, an elementary geometric reasoning shows that D intersects the circle $\partial \bar{B}_p$ in two points that lie in Q. Thus, $\mathcal C|_{c}^{p}$ does not contain neither a nor b, which is absurd.

• 2. This part of the proof is illustrated by Fig. 2 (right). Let us consider a point q in $S\setminus \left( S\ominus \bar{B}(0,\delta /2) \right)$ and $q\notin \mathcal C$ (if $q\in \mathcal C$, we are done by Part 1). Then, there exists a point $p\in \mathcal C$ such that $\mathrm d(p,q)=\mathrm d(q,\mathcal C)<\delta /2$. Thereby, the open disk $B(q,\mathrm d(p,q))$ is included in the interior of S. With the notations of Part 1, we consider the sector A of $\bar{B}_p$ containing q and delimited by [a, p, b] where a and b are the endpoints of $\mathcal C\cap \bar{B}_p$. Let $R=[p,c]$ be the radius of $\bar{B}_p$ passing through q. If the arc $\mathcal C_{a,p}$, resp. $\mathcal C_{b,p}$, cuts the radius R, thanks to Proposition 2, we have that the turn of $\mathcal C_{a,p}$, resp. $\mathcal C_{b,p}$, is greater than the turn of a quarter of circle and, as in Part 1, we derive a contradiction with Fenchel’s Theorem (Property 1). Thus, $\mathcal C_{a,b}$ does not intersect the radius R. We end the proof as in Part 1, just noticing that the angular sector $\bigcap \{d\mid d\in D\}$ does contain the radius R which ensures the existence of a square in S including R, and thus containing q.

• 3. When the considered point lies in $S\ominus \bar{B}(0,\delta /2)$, the result follows from the very definition of the operator $\ominus$.

Eventually, we partitioned the set S in three subsets and in each of these subsets we proved that any point is contained in a square with diameter $\delta$ included in S. Hence, the result holds.    $\square$

Fig. 2.

Left: the turn of the polyline [a,q,p,b], $\gamma +\delta$, is greater than $\alpha +\delta =\pi$ (the half-line passing through p and q is the bisector of the angle $\widehat{apb}$). Center: in blue the arc $C_{a,b}=\mathcal C\cap \bar{B}(p,\frac{\delta }{\sqrt{2}})$. In red, another arc of $\mathcal C$ whose end c is inside a square having p for vertex and included in the shape bounded by $\mathcal C$. Right: in blue, the arc $\mathcal C_{a,b}=\mathcal C\cap \bar{B}(p,\frac{\delta }{\sqrt{2}})$. The disk $\bar{B}(p,\mathrm d(p,q))$ is included in the shape bounded by $\mathcal C$. Since the arc $\mathcal C_{a,b}$ cuts the radius [p, c] passing through q, its turn is greater than that of the quarter of circle in red.

Thanks to the previous proposition, we get in Corollary 1 that a shape S having a $\delta$-LTB curve for boundary with $r \le {\delta }/{(2\sqrt{2})}$ verifies the two last items of Definition 4 with $r'= \sqrt{2} r$ and that $S \ominus \bar{B}(0,r)$ is non-empty.

Corollary 1

Let S be closed shape having a $\delta$-LTB curve $\mathcal C$ for boundary. Let $r \le \delta / ({2}{\sqrt{2}})$. Then,

• $S \ominus \bar{B}(0,r)$ is non-empty,

• $S \subset S \ominus \bar{B}(0,r) \oplus \bar{B}(0, \sqrt{2} r)$,

• $S^c \subset S^c \ominus \bar{B}(0,r) \oplus \bar{B}(0, \sqrt{2} r)$,

Proof

Let $p \in S$. By Proposition 3, there exists a square Q of edge length 2r containing p and included in S. Then, the center q of Q belongs to $S\ominus \bar{B}(0,r)$ which is therefore non-empty. Furthermore, $Q\subseteq S\ominus \bar{B}(0,r)\oplus \bar{B}(0, \sqrt{2}r)$. Then, $S\subseteq S\ominus \bar{B}(0,r)\oplus \bar{B}(0, \sqrt{2}r)$. Alike, applying Proposition 3 to $\bar{S^c}$, we get $S^c \subset S^c \ominus \bar{B}(0,r) \oplus \bar{B}(0, \sqrt{2} r)$.    $\square$

It remains to prove that the erosion by a disk of radius r of a connected component of the plan deprived of a LTB curve is path connected (for well chosen values of $r/\delta$). The rest of the proof is made by contradiction: we assume that $S \ominus B(0,r)$ has at least two distinct connected components and we consider the infimum distance $d_0$ between two connected components. The reasoning is split into two cases: $d_0 \le 2\sqrt{2} r$ (Lemma 1) and $2\sqrt{2} r < d_0$ (Lemma 2).

Lemma 1

Let $\mathcal C$ be a $\delta$-LTB curve and A be a connected component of $\mathbb R^2\setminus \mathcal C$. Let $r< {\delta }/{\sqrt{10+4\sqrt{2}}}$. Two points of $\partial (A \ominus \bar{B}(0,r))$ at distance less than or equal to $2\sqrt{2} r$ are path-connected in $A \ominus \bar{B}(0,r)$.

Proof

Let $x_0$ and $x_1$ two points of $A \ominus \bar{B}(0,r)$ at distance less than or equal to $2\sqrt{2} r$ from each other (Fig. 4 illustrates the proof). Assume that the segment $[x_0,x_1]$ is not included in $A \ominus \bar{B}(0,r)$ (otherwise, we are done). Then, there exists a point $a\in \mathcal C$ in the dilation of the segment $[x_0,x_1]$ by the open disk B(0, r) deprived of the two closed disks with center $x_0$, $x_1$ and radius r. Thereby, the point a belongs to a rectangle $[x_0, u_0, u_1, x_1]$ with $u_0 \in \partial B(x_0, r)$ and $u_1 \in \partial B(x_1, r)$. Since the segment $[x_0, x_1]$ is not included in $A \ominus \bar{B}(0,r)$, we are going to build another arc from $x_0$ to $x_1$ that will be proved to lie inside $A \ominus \bar{B}(0,r)$. Let $i_0$ and $i_1$ be the respective intersections of the segment $[x_0,x_1]$ with the circles $\partial \bar{B}(x_0,r)$ and $\partial \bar{B}(x_1,r)$. For $k \in \{0,1 \}$, let $l_k$ be the symmetric of $u_k$ with respect to $x_k$. Let $p_0$ and $p_1$ be the intersection points of the segment $[l_0,l_1]$ and the circles $\partial B(i_0,r)$ and $\partial B(i_1,r)$. Let P be the simple arc $\overset{\frown }{x_0i_0p_0}\cup [p_0,p_1]\cup \overset{\frown }{p_1i_1x_1}$ where $\overset{\frown }{xcy}$ denotes the quarter of circle with center c linking the points x and y. We claim that P is included in $A \ominus \bar{B}(0,r)$. By contradiction, assume that $P\nsubseteq A \ominus \bar{B}(0,r)$. Then, there exists a point $b\in \mathcal C\cap \big (P\oplus B(0,r)\big )$ deprived of $B(x_0,r)$ and $B(x_1,r)$. The distance between a and b is upper-bounded by the distance between $o_0$ and $u_1$ ($o_0$ is the symmetric of $i_0$ with respect to $x_0$), that is by $\sqrt{10+4\sqrt{2}}r$. Thus, $\mathrm d(a,b)<\delta$. Therefore, there exists a straightest arc $\mathcal C|_{a}^{b}$ between a and b. We set $X=\mathbb R^2\setminus (B(x_0,r) \cup B(x_1, r) )$. For $k \in \{0,1 \}$, let $H_k$ be the set of simple arcs $\mathcal D_{a,b}$ in X between a and b such that any arc between a and b homotopic to $\mathcal D_{a,b}$ in X intersects the quarter of plane $Q_k$ delimited by the rays $\overrightarrow{ \mathrm x_ko_k}$ and $\overrightarrow{ \mathrm x_ku_k}$. Alike, let I be the set of simple arcs $\mathcal D_{a,b}$ in X between a and b such that any arc between a and b homotopic to $\mathcal D_{a,b}$ in X intersects the segment $[x_0, x_1]$ (see Fig. 3). Notice that I is empty if $\mathrm d(x_0,x_1)\le 2r$. Observe that any arc between a and b in X that does not intersect the segment $[x_0, x_1]$ belongs to $H_0\cup H_1$. Furthermore, by definition of $H_0$ and $H_1$, any arc between a and b in X homotopic to an arc not in $H_0\cup H_1$ is not in $H_0\cup H_1$ and thereby intersects $[x_0,x_1]$. Then, any arc between a and b in X that is not in $H_0\cup H_1$ is in I.

In other words, we split the set of simple arcs between a and b in X in two classes: those passing in between the disks $B(x_0,r)$ and $B(x_1, r)$ and the others that turn around $B(x_0,r)$ or $B(x_1, r)$. Be aware that actually this splitting is not a partition for we make no restriction about the turn of the arcs in both sets. Hence, these arcs can do several turns around any of the two disks. The problem is that the only tool to link homotopy and turn to our knowledge is Proposition 2 and it is not sufficient to easily constrain the behavior of the arcs.

• Firstly, assume that the arc $\mathcal C|_{a}^{b}$ belongs to I. Let z be a point of intersection of the arc $\mathcal C|_{a}^{b}$ and the segment $[i_0, i_1]$.

  • Let $t_0$ and $t_1$ be the tangents from z to the quarters of circle $\overset{\frown }{i_0x_0u_0}$ and $\overset{\frown }{i_1x_1u_1}$ at points $q_0$ and $q_1$. Put $\alpha _k:= \widehat{i_k x_k q_k}$ for $k \in \{0,1 \}$. Since $\mathrm d(x_0, x_1) \le 2 \sqrt{2} r$ and the secant function is increasing and strictly convex, we derive

    $$\begin{aligned} \sec \left( \frac{\alpha _0+ \alpha _1}{2}\right) \le \frac{\sec (\alpha _0)+\sec (\alpha _1)}{2} \le \sqrt{2}\le \sec (\frac{\pi }{4}), \end{aligned}$$

    (1)

    that is $\alpha _0+\alpha _1\le \pi /2$ and the equality occurs only if $\alpha _0=\alpha _1= \frac{\pi }{4}$. Since $\widehat{q_0zq_1}= \alpha _0+ \alpha _1$, we get $\widehat{q_0zq_1}\le \frac{\pi }{2}$.

  • According to Proposition 3, there exists a square S with edge length $\delta /\sqrt{2}$, having z for vertex and whose interior is included in the exterior of A. Observe that, since $\mathrm d(x_0,x_1)\le 2\sqrt{2}r$, the distances $\mathrm d(q_0, z)$ and $\mathrm d(q_1, z)$ are upper-bounded by $\mathrm d(i_0, u_1)=\sqrt{10-4\sqrt{2}}r$ which is less than the edge length of S. Thus, the square S has to be included in the sector delimited by the tangents $t_0$ and $t_1$ and not containing $x_0$ and $x_1$. Then, $\widehat{q_0zq_1}\ge \frac{\pi }{2}$, and by Eq. 1, $\alpha _0= \alpha _1= \frac{\pi }{4}$, that is z is the middle of $[i_0, i_1]$. Therefore, z is the unique point of $\mathcal C$ lying on $[i_0,i_1]$.

  • Noting that the three points $q_0$, $q_1$ and z are at distance less than $\delta /2$ from each other, we derive from [8, Lemma 8.a] that one of the three subarcs of $\mathcal C$ delimited by the three points z, $q_0$, $q_1$ has a turn greater than $\pi /2$. Since $\kappa ([q_0,q_1,z])>\pi /2$ and $\kappa ([q_1,q_0,z])>\pi /2$, the arc of $\mathcal C$ between $q_0$ and z not containing $q_1$ and the arc of $\mathcal C$ between $q_1$ and z not containing $q_0$ have a turn bounded from above by $\pi /2$. Thus, the third arc delimited by the three points z, $q_0$, $q_1$, which is the arc between $q_0$ and $q_1$ not containing z has a turn greater than $\pi /2$. Hence, the turn of the arc $\mathcal C_{{q_0},{q_1}}$ between $q_0$ and $q_1$ containing z is less than or equal to $\pi /2$. As the $\kappa (\mathcal C_{{q_0},{q_1}})\ge \kappa (\widehat{q_0,z,q_1})=\pi /2$ by the definition of the turn, we derive that $\kappa (\mathcal C_{{q_0},{q_1}})=\pi /2$. Thus, $\mathcal C_{{q_0},{q_1}}$ is the polyline $[q_0,z,q_1]$. Then, the arc $\mathcal C|_{a}^{b}$ is the disjoint union of two or three arcs, an arc $\mathcal C_k$ between a and a point $q_k$, $k\in \{0,1\}$, the open polyline $(q_0,z,q_1)$ and an arc $\mathcal C_{1-k}$ between $q_{1-k}$ and b if $a\notin [q_0,z,q_1]$, or the polyline $[a,z,q_{1-k})$ and the arc $\mathcal C_{1-k}$ if $a\in [q_k,z)$. Thus, $\mathcal C|_{a}^{b}$ is homotopic in X to $\mathcal C_k\sqcup (q_0,q_1)\sqcup \mathcal C_{1-k}$, or to $[a,q_{1-k})\sqcup \mathcal C_{1-k}$ which do not intersect $[x_0,x_1]$ (for z is the unique point of $\mathcal C$ on $[i_0,i_1]$ and $\mathcal C$ is simple). Contradiction!

• Secondly, assume that for some $k\in \{0,1\}$, $\mathcal C|_{a}^{b} \in H_k$ . We denote by $O_k$, $k\in \{0,1\}$, the convex hull of the quarter of the circle $\partial B(x_k,r)$ delimited by $u_k$ and $o_k$.

  $O_k$ is included in a bounded component of $\mathbb R^2\setminus (\mathcal C|_{a}^{b} \cup [a,b])$. Then, according to the definition of $\mathcal C|_{a}^{b}$ and Proposition 2,

  $$\pi /2\ge \kappa (\mathcal C|_{a}^{b})\ge \kappa (\partial {\text {conv}}(O_k\cup [a,b])\setminus (a,b))>\pi /2,$$

  which is absurd (the last inequality comes from the fact that a, resp. b, cannot lie on the tangent at $u_k$, resp. $o_k$, to the circle $\partial B(x_k,r)$).

Finally, in each studied case, the assumption that the path P is not included in the eroded set $A\ominus \bar{B}(0,r)$ leads to a contradiction. We conclude that the points $x_0$ and $x_1$ are path-connected in $A\ominus \bar{B}(0,r)$.    $\square$

Fig. 3.

On the left the blue arc belongs to the set $H_0$, the green arc to I and the red arc to $H_1$. On the right, the purple arc belongs to $H_0$, $H_1$ and I. (Color figure online)

Fig. 4.

The figure illustrates the notations used in the proof of Lemma 1. The proof consists in showing that one of the two red paths joining the points $x_0$ $x_1$ is included in $A \ominus \bar{B}(0,r)$.

Lemma 2

Let S be a closed subset of $\mathbb R^2$ whose boundary is a $\delta$-LTB curve. Let $r < \frac{\sqrt{2}}{2}\delta$. The minimal distance $d_0$ between two connected components of the eroded shape $S \ominus \bar{B}(0,r)$ (respectively $S^c \ominus \bar{B}(0,r)$) is upper-bounded by $2\sqrt{2} r$.

Proof

Assume by contradiction that $d_0 > 2 \sqrt{2} r$. Let A be $S \ominus \bar{B}(0,r)$ (the case $A=S^c \ominus \bar{B}(0,r)$ is similar). If A has two, or more, connected components, then it is the same with $A\oplus \bar{B}(0,\sqrt{2} r)$ for the dilation of a path connected set by a path connected structural element containing the origin is path connected and the radius of the dilation is less than the half of $d_0$. Therefore, S, which is connected and included in $A\oplus \bar{B}(0,\sqrt{2} r)$ is included in just one connected component of $A\oplus \bar{B}(0,\sqrt{2} r)$. Therefore, the others components do not contain any point of S. Hence, there are at least one non empty component of $S\ominus \bar{B}(0,r)$ which does not contain any point of S which is absurd.    $\square$

Proof

(Theorem 1).

By Corollary 1:

• $S \ominus \bar{B}(0,r)$ is non-empty,

• $S \subset S \ominus \bar{B}(0,r) \oplus \bar{B}(0, \sqrt{2} r)$,

• $S^c \subset S^c \ominus \bar{B}(0,r) \oplus \bar{B}(0, \sqrt{2} r)$.

Assume by contradiction that $S \ominus \bar{B}(0,r)$ or $S^c \ominus \bar{B}(0,r)$ is not path-connected. Since S is a compact set, S can be covered by a finite number of disks of radius $\frac{r}{2}$, then $S \ominus \bar{B}(0,r)$ is also covered by a finite number of disks of radius $\frac{r}{2}$. Moreover, by Lemma 1, in each disk of radius $\frac{r}{2}$ there is at most one connected component of $S \ominus \bar{B}(0,r)$. Then $S \ominus \bar{B}(0,r)$ has a finite number of connected components. Since S is compact, $S^c\ominus \bar{B}(0,r)$ has just one unbounded component, say $S^c_0$, and $(S^c\ominus \bar{B}(0,r))\setminus S^c_0$ is bounded. Thereby, by the same reasoning as for $S\ominus \bar{B}(0,r)$, we have that $S^c\ominus \bar{B}(0,r)$ has a finite number of connected components. Then the minimal distance $d_0$ between two connected components is well-defined for both $S \ominus \bar{B}(0,r)$ and $S^c \ominus \bar{B}(0,r)$. More precisely, $d_0$ is defined by:

$$\begin{aligned} d_0:= \min \left\{ \inf _{x_0 \in A_0, x_1 \in A_1} \mathrm d(x_0,x_1) | A_0, A_1 \text { distinct connected components of } A \right\} , \end{aligned}$$

where A is $S \ominus \bar{B}(0,r)$ or $S^c \ominus \bar{B}(0,r)$. But by Lemmas 1, 2, $d_0 \notin [0, 2 \sqrt{2} r] \cup (2 \sqrt{2} r, + \infty )$. Contradiction !    $\square$

4 Conclusion

This paper establishes that the Local Turn Boundedness implies the quasi-regularity in 2D. Therefore the set of quasi(r)-regular curves is larger than the set of LTB curves for a $r<{\delta }/{\sqrt{10+4\sqrt{2}}}$. On the one hand, quasi-regularity allows the corresponding shape digitization to keep its convexity and its topological properties under rigid motion [10, 11]. On the other hand, Local Turn Boundedness has been introduced to map ordered samplings of the digital boundary to close ordered samplings of the continuous curve in order to compare the lengths of the continuous curve and of its digitization.

It is possible to build a quasi(r)-regular curve having arbitrary numerous small (against r) oscillations leading to an arbitrary large length. Thus, the results obtained in [8] on the length estimation of LTB curves cannot be extended to quasi-regular curves. Nevertheless, the link between Local Turn Boundedness and quasi-regularity can be useful for the generalization of Local Turn Boundedness to higher dimension and this is the perspective of our work.