Augustin Fruchard

Tudor Zamfirescu

Cages of small length holding convex bodies

Keywords: AMS Classification: 52A15, 52A40, 52B10 Immobilisation, skeleton, Steiner tree, convex body

Cages of small length holding convex bodies

Augustin Fruchard, Tudor Zamfirescu

Introduction

A cage is the 1-dimensional skeleton of a convex polytope in R 3 . A cage G is said to hold a compact set K disjoint from G if no rigid motion can bring K in a position far away without meeting G on its way. Already in 1959, Coxeter [5] raised the problem of finding a cage of minimal total length holding the ball of radius 1 in R 3 . In the following years, Besicovitch and Aberth solved Coxeter's problem. In the present paper, we extend the investigation to other compact convex sets replacing the ball.

The space R 3 is endowed with its euclidean norm x =

x, x , where , is the usual scalar product. For distinct x, y ∈ R 3 , let xy be the line through x, y and xy the line-segment from x to y. The open segment xy \ {x, y} is denoted by ]xy[. Given a line xy oriented from x to y, (xy) + denotes the open half-plane on the left of xy. As usual, for M ⊂ R d with d ≥ 2, bdM denotes its boundary, relbdM denotes its relative boundary, and diamM = sup x,y∈M xy ∈ R ∪ {+∞}. Its convex hull convM is the intersection of all convex subsets of R d containing M , and its affine hull affM is the intersection of all affine subspaces of R d containing M . For any closed convex subset M of R 3 , let π M : R 3 → M denote the (metric) projection, i.e. π M (x) is the unique point of M such that xπ M (x) = inf y∈M xy . It is known (and easy to prove) that xπ M (x), yπ M (x) ≤ 0 for all y ∈ M and that π M is 1-Lipschitz. Here, a 2-or 3-dimensional compact convex set in R 3 is called a convex body. Let K be the space of all convex bodies in R 3 . For K ∈ K, we denote by widK the smallest distance between two parallel (dim K -1)-dimensional affine subspaces H, H ′ of affK such that K ⊂ conv(H ∪ H ′ ). The d-dimensional unit ball (centred at 0) is denoted by B d , and relbdB d = S d-1 (d ≥ 2). The d-dimensional regular simplex of edge length 1 is denoted by T d (d ≥ 2). The d-dimensional cube of unit edge length is denoted by C d (d ≥ 2). We shall denote by λ the 1-dimensional Hausdorff measure (length).

For n ≥ 2 and x 1 , x 2 , . . . , x n ∈ R 2 , we put x 1 x 2 . . . x n = conv{x 1 , x 2 , . . . , x n } and |x 1 x 2 . . . x n | = λbdx 1 x 2 . . . x n . In particular |xy| = xy . Given x 1 , . . . , x n ∈ R 3 , the perimeter function is p(x 1 , . . . , x n ) = n i=1 |x i x i+1 | (with x n+1 = x 1 ). If x 1 , . . . , x n are coplanar and in convex position, i.e. x 1 . . . x n is a non degenerate convex n-gon with consecutive vertices x 1 , . . . , x n , then p(x 1 , . . . , x n ) = |x 1 . . . x n |, but p(x 1 , x 2 ) = 2|x 1 x 2 |.

Let G(K) be the space of all cages in R 3 holding the compact set K and set

L(K) = inf G∈G(K) λG.
We are looking for L(K) for various sets K. Apart from general results, we estimate L(K) for the most common convex bodies. For the unit balls we find L(B 2 ) = 6, while L(B 3 ) = and L(T 3 ) = 3. For the cubes of unit edge length, we establish L(C 2 ) = 3 √ 2 and L(C 3 ) ≤ 4 + 3 √ 2. We conjecture that L(C 3 ) = 4 + 3 √ 2. The structure of the article is as follows. In Section 2 we relate the length of a cage with the perimeter and the length of the Steiner tree joining the projections of the vertices of the cage on some plane; this will yield lower bounds for L(K) for several sets K. Section 3 deals with the notion of almost fixing points, yielding upper bounds for L(K). Planar convex bodies are studied in Section 4 and nonplanar ones in Section 5.

We end this introductory section with the following result.

Theorem 1. The function L is upper semi-continuous, but not continuous.

Proof. Let K be a compact convex set, and ε > 0. Assume without loss of generality that 0 ∈ intK. By definition, K admits a cage G holding K of length less than L(K) + ε. As K and G are disjoint, there exist ν < 1 < µ such that µK and νG are disjoint too. Clearly, νG holds νK. Thus, each convex compact set K ′ satisfying νK ⊂ K ′ ⊂ µK is held by νG. Hence, for each K ′ in a suitable neighbourhood of K, L(K ′ ) ≤ λ(νG) ≤ λG ≤ L(K) + ε, and thus L is upper semicontinuous. That L is not continuous it can be seen as follows. Take the square S = C 2 = abcd. For 0 < η < 1, let x ∈ ab satisfy |xa| = η and choose S η = xbcd. Then S η → S if η → 0, but we have L(S η ) = 3 for all η, as shows Theorem 7 (i) in the sequel, while L(S) = 3 √ 2, as shows Theorem 8 (ii).

Planar graphs and Steiner trees

By a geometric graph, we mean a pair (G, η), where G is a graph with vertex set V (G) and edge set E(G), and η is an embedding of G in a plane Π, which acts as follows. For any vertex

v ∈ V (G), η(v) is a point in Π; for any edge (v, w) ∈ E(G), η((v, w)) is the line-segment η(v)η(w) ⊂ Π, reduced to {η(v)} if η(v) = η(w).
The set ∪ e∈E(G) η(e) will be denoted by η(G). Observe that we may have η(v) ∈ η((u, w)) for distinct v, u, w ∈ V (G), and η((u, v))∩η((u ′ , v ′ )) may be non-void, even a line-segment, for distinct u, v, u

′ , v ′ ∈ V (G). A vertex v ∈ V (G) is called external if η(v) ∈ bdconvη(G), and an edge e ∈ E(G) is called external if η(e) ⊂ bdconvη(G). If 1) η(G) is not a line-segment, 2) for any point x ∈ Π, card η |v(G) -1 ({x}) ≤ 2,
3) for any side s = ab of the convex polygon convη(G), there is at least one

path (v 1 , . . . , v n ) in G such that η(v 1 ) = a, η(v n ) = b, and η((v 1 , . . . , v n )) = ab, then (G, η) is called convex.
We denote by P s one of the paths (v 1 , . . . , v n ) satisfying condition 3). Notice that condition 3) implies that the union of η(e) for all external edges e equals bd convη(G). Now, for every side s of convη(G), delete from G the edges of P s , to obtain a graph ∇G.

We call a geometric graph (G, η) strongly connected if G has at least three edges and the graph G \ {e For the geometric graph (G, η), we define its length µ(G, η) as follows.

µ(G, η) = λη ∇G + λbdconvη(G).

Consider n points v 1 , . . . , v n ∈ R 3 . Let S(v 1 , . . . , v n ) denote the length of the shortest rectifiable set containing all n points, called their Steiner tree. Moreover, let

f (v 1 , . . . , v n ) = p(v 1 , . . . , v n ) + S(v 1 , . . . , v n ), ( 1
)
where p is the perimeter function. Remember that

f (v 1 , . . . , v n ) = |v 1 . . . v n | + S(v 1 , . . . , v n ) if n ≥ 3 and v 1 , . . . , v n are coplanar and in convex position in the plane, but f (v 1 , v 2 ) = 3|v 1 v 2 |.
The function f will play a central role in this article. An immediate consequence of Lemma 2.1 is the following.

Corollary 2.2. Let (G, η) be a convex strongly connected geometric graph, with external vertices v 1 , . . . , v n such that η(v 1 ), . . . , η(v n ) lie in this order on bd convη(G). Then

µ(G, η) ≥ f η(v 1 ), . . . , η(v n ) . Indeed, µ(G, η) = λη ∇G + λbd convη(G) ≥ S η(v 1 ), . . . , η(v n ) + p η(v 1 ), . . . , η(v n ) = f η(v 1 ), . . . , η(v n ) .
We shall use the following obvious fact.

Lemma 2.3. If ϕ : R 3 → R 3 is 1-Lipschitz, then p ϕ(v 1 ), . . . , ϕ(v n ) ≤ p(v 1 , . . . , v n ),
S ϕ(v 1 ), . . . , ϕ(v n ) ≤ S(v 1 , . . . , v n ), and therefore

f ϕ(v 1 ), . . . , ϕ(v n ) ≤ f (v 1 , . . . , v n ).
Theorem 2. Let G be a cage and P some plane in R 3 . If v 1 , . . . v n are the external vertices of (G, π P ) such that π P (v 1 ), . . . , π P (v n ) lie in this order on bd convη(G), then λG ≥ f π P (v 1 ), . . . , π P (v n ) .

Proof. As a graph, the 1-dimensional skeleton of a polytope is 3-connected (i.e., every pair of vertices can be joined by three paths in the graph having only their endpoints in common), and therefore 3-edge connected (i.e., the graph minus any pair of edges is graph-theoretically connected). Then the geometric graph (G, π P ) is strongly connected. Also, it is easily verified that (G, π P ) is convex. We have G = ∇G ∪ ∪ s P s and λG = λ∇G + s λP s . By successively using Lemma 2.3 and Corollary 2.2, we obtain Indeed, on the one hand, the normal to the ellipse at d must bissect the angle ∠adb, on the other hand, denoting by ω the centre of C, we have ∠adc = 1 2 ∠aωc = π 3 = ∠cdb. It follows that both normals to the ellipse and to the cercle of centre c coincide at d. Now, the convex curve O + (a, b, k) is fully described via the symmetry with respect to the bisector of ab, and further O(a, b, k) via the symmetry with respect to ab.

λG ≥ λπ P ∇G + s λπ P (P s ) ≥ µ(G, π P ) ≥ f π P (v 1 ), . . . , π P (v n ) .
(ii) Put k = S(a, b, x), let D x be the tangent of O(a, b, k) at x, and choose for H x (a, b) the half-plane bounded by D x and not containing ab.

Remark. One can prove that, for all integers n ≥ 3, all a 1 , . . . , a n ∈ R 2 , and all k > S(a 1 , . . . , a n ), the locus {x ∈ R 2 ; S(a 1 , . . . , a n , x) = k} is a concatenation of convex C 1 curves, themselves concatenations of arcs of circles and/or ellipses, with possible angular points b 1 , . . . , b r . These points b j are those for which the Steiner tree of a 1 , . . . , a n , b j is not unique, and where this Steiner tree combinatorially changes.

Corollary 2.5. If v 1 , . . . , v n ∈ R 2 and a, b, c ∈ v 1 . . . v n , then S(a, b, c) ≤ S(v 1 , . . . , v n ) and f (a, b, c) ≤ f (v 1 , . . . , v n ).
Proof. Since c (resp. b, a) is in the convex hull of v 1 , . . . , v n , every half-plane bounded by a straight line passing through c (resp. b, a) contains at least one point v

i (resp. v j , v k ). Choose c ′ = v i in the half-plane H c (a, b) given by Proposition 2.4 (ii). Similarly, choose b ′ = v j in the half-plane H b (a, c ′ ), then choose a ′ = v k in the half-plane H a (b ′ , c ′ ). Then we have S(a, b, c) ≤ S(a, b, c ′ ) ≤ S(a, b ′ , c ′ ) ≤ S(a ′ , b ′ , c ′ ) = S(v k , v j , v i ) ≤ S(v 1 , . . . , v n ). Since |abc| ≤ |v 1 . . . v n |, the inequality for f follows. ✔ ✔ ✔ ✔ ✔ ✔ ✔ ✔ ✔ ❚ ❚ ❚ ❚ ❚ ❚ ❚ ❚ ❚ ❚ ❚ ❚ ❚ ❚ ✔ ✔ ✔ ✔ ✔ ❉ ❉ ❉ ❉ ❉ ❉ ❉ ❉ ❉ ❉ ❉ ❉ ❉ ❉ ❉ ❉ ❉ ❉ ❉ ❉ ❉ ❉ ❉ ❉ ❉ ❉ ❉ ❉ ❉ ★ ★ ★ ★ ★ ★ r a 1 = a r b = a 2 r c = a 3 r a 4 r d r t Figure 2:
In bold, a Steiner tree connecting a 1 , . . . , a 4 .

Remark. One could expect that, for a 1 , . . . , a m ∈ v 1 . . . v n , we have S(a 1 , . . . , a m ) ≤ S(v 1 , . . . , v n ) as soon as m < n. This is however false, already for m = 4. Indeed, given an equilateral triangle T 2 = abc of unit edge length, choose n points v 1 , . . . , v n , some of them close to a, some close to b, and others close to c, such that abc is in their convex hull. Then

S(v 1 , . . . , v n ) is close to S(a, b, c) = √ 3, while for a 1 = a, a 2 = b, a 3 = c, a 4 = 1 2 (a + b),
one can check that one of the Steiner trees connecting a 1 , . . . , a 4 is obtained by joining a 1 to a 4 , then taking the Steiner tree of a 2 , a 3 and a 4 , cf. Figure 2; the other Steiner tree is symmetric with respect to the line a 3 a 4 . If d is such that a 2 , a 4 , d is equilateral and if t is the Fermat-Torricelli point associated to a 2 , a 3 , a 4 , from

|ta 4 | + |ta 2 | = |td| one obtains S(a 1 , . . . , a 4 ) = |a 1 a 4 | + |a 3 d| = 1 2 1 + √ 7 > S(v 1 , . . . , v n ).
Theorem 3. Let K be a planar convex body, x, y, z ∈ bdK, and x ′ , y ′ , z ′ ∈ R 2 , such that xx ′ , yy ′ , zz ′ , are supporting lines of K and the vectors x ′x, y ′y, z ′z point toward the direct sense on bdK. Assume that the order of x, y, z is also in the direct sense on bdK and that the Steiner tree determined by x, y, z has a vertex v inside intK. Put α x = ∠x ′ xy, β x = ∠x ′ xv, γ x = ∠x ′ xz, and, analogously, α y , β y , γ y and α z , β z , γ z . If f attains a local minimum at x, y, z, then

cos α x + cos β x + cos γ x = 0, cos α y + cos β y + cos γ y = 0, cos α z + cos β z + cos γ z = 0.
Moreover, bdK is differentiable at x, y, z, and the normals at x, y, z are concurrent. Proof. Consider for a moment v = (v 1 , v 2 ), y = (y 1 , y 2 ) and z = (z 1 , z 2 ) fix, and x variable on

z y x v x ′ z ′ y ′ α x β x γ x bdK T = xx ′
T = xx ′ . Put g(x) = |xy| + |xv| + |xz|.
Again for a moment, consider T to be the real line R × {0}, with the real number x corresponding to the point x as its abscissa. We have

g(x) = (x -y 1 ) 2 + y 2 2 + (x -v 1 ) 2 + v 2 2 + (x -z 1 ) 2 + z 2 2 , whence g ′ (x) = x -y 1 (x -y 1 ) 2 + y 2 2 + x -v 1 (x -v 1 ) 2 + v 2 2 + x -z 1 (x -z 1 ) 2 + z 2 2 = cos α x + cos β x + cos γ x . Now, assume cos α x + cos β x + cos γ x = 0.
Then, for some x ∈ T close to x, g( x) < g(x). This implies

|zπ K ( x)|+|vπ K ( x)|+|yπ K ( x)| < g(x)
, which yields f ( x, y, z) < f (x, y, z), impossible.

To prove the second part, suppose that some normals at x, y, z form a non-degenerate triangle.

Then suitably and slightly turning the set {v, x, y, z} about an interior point of that triangle brings all three points x, y, z in positions x ′′ , y ′′ , z ′′ outside K. But then

f (π K (x ′′ ), π K (y ′′ ), π K (z ′′ )) < f (x, y, z),
which is again impossible.

In the rest of this Section, we compute the infimum of f on some sets; this will be useful in Section 4.

Lemma 2.6. We have inf{f (x, y, z) ; x, y, z ∈ S 1 , 0 ∈ xyz} = 6.

Proof. Recall the perimeter function p, here defined by p(x, y, z) = |xyz| if all three points are distinct and p(x, y, y) = 2|xy|. It is easily seen that both p and S have no local minimum with distinct x, y, z. It follows that the global minimum of both functions is attained when two of the points x, y, z collapse, i.e. when xyz is a diameter of S 1 .

Lemma 2.7. If abc is an equilateral triangle of sides I 1 = bc, I 2 = ca, I 3 = ab and side length δ, then inf{f (u 1 , u 2 , u 3 ) ;

u k ∈ I k } = 3+ √ 3 2 δ. This infimum is reached precisely at (a ′ , b ′ , c ′ )
, where a ′ , b ′ , c ′ are the midpoints of bc, ca, ab respectively.

Proof. We prove that both functions p and S have a global minimum on I 1 ×I 2 ×I 3 at (a ′ , b ′ , c ′ ), and that this minimum is uniquely reached for p. The minimality of p implies the so-called incidence/reflection law: ∠cu 1 u 2 = ∠u 3 u 1 b, denoted by α, and similarly ∠au 2 u 3 = ∠u 1 u 2 c = β and ∠bu 3 u 1 = ∠u 2 u 3 a = γ. Since the angles in a triangle sum to π, we have α

+ β = β + γ = γ + α = 2π 3 , yielding α = β = γ = π 3 . It follows that the minimum of p is reached only at (a ′ , b ′ , c ′ ).
For S, however, there is a 2-dimensional subset of I 1 × I 2 × I 3 where S attains its global minimum: choose arbitrarily t ∈ abc and consider u 1 = π bc (t), u 2 = π ca (t), and

u 3 = π ab (t). Then t is the Fermat-Torricelli point t(u 1 , u 2 , u 3 ) and S(u 1 , u 2 , u 3 ) = √ 3 2 δ. Lemma 2.8. If abcd is a parallelogram of sides I 1 = ab, I 2 = bc, I 3 = cd, I 4 = da, with δ = |ac| ≤ |bd|, then inf{f (u 1 , . . . , u 4 ) ; u k ∈ I k } = 3δ.
If abcd is not a rectangle, then this infimum is reached precisely at (a, c, c, a). If abcd is a rectangle, then the infimum is reached at both (a, c, c, a) and (b, b, d, d).

Proof. As before, we prove that both functions p and S have a global minimum at the aforementioned points. Assume that abcd is not a rectangle, and put β = ∠abc. We have β < π 2 . Firstly, observe that the perimeter function p has no local minimum at a quadruple (u 1 , . . . , u 4 ) with u i / ∈ {a, b, c, d} for every i. Indeed, at such four points, the minimality of p implies the incidence/reflection law, which yields 4β = 2π, a contradiction. Hence the minimum is attained, say, for u 1 = a or b. Then one easily shows that u 4 = u 1 in the first case and u 2 = u 1 in the second, and finally that the global minimum of p is attained at the Steiner tree connecting u 1 , . . . , u 4 , let x 1 be the neighbour of u 1 , and x 3 that of u 3 . Then

u 1 = u 4 = a, u 2 = u 3 = c. In ❈ ❈ ❈ ❈ ❈ ❈ ❈ ❈ ❈ ❈ ❈ ❈ ❈ ❈ ❈ ❈ ❵ ❵ ❵ ❵ ❵ ❇ ❇ ❇ ❇ ✡ ✡ ✡ ✡ ❆ ❆ ❤ ❤ ❤ ❤ ❤ r r r r r r r r r r r r a b β c d u 1 u 2 u 3 u 4 x 1 x 3 π ab (x 1 ) π cd (x 3 ) ❈ ❈ ❈ ❈ ❈ ❈ ❈ ❈ ❈ ❈ ❈ ❈ ❈ ❈ ❈ ❈ ✥ ✥ ✥ ✥ ✥ ✂ ✂ ✂ ✂ ❏ ❏ ❏ ❏ ✁ ✁ ✭ ✭ ✭ ✭ ✭ ✭
S(u 1 , . . . , u 4 ) = |u 4 x 1 | + |u 1 x 1 | + |x 1 x 3 | + |x 3 u 3 | + |x 3 u 2 | ≥ |aπ ab (x 1 )| + |π ab (x 1 )x 1 | + |x 1 x 3 | + |x 3 π cd (x 3 )| + |π cd (x 3 )c| ≥ |ac| if x 1
is the neighbour of u 4 and x 3 the neighbour of u 2 in the Steiner tree (see Fig. 4, left), and

S(u 1 , . . . , u 4 ) = |u 4 x 3 | + |u 3 x 3 | + |x 3 x 1 | + |x 1 u 1 | + |x 1 u 2 | ≥ |π cd (a)π cd (x 3 )| + |π cd (x 3 )x 3 | + |x 3 x 1 | + |x 1 π ab (x 1 )| + |π ab (x 1 )π ab (c)| ≥ |π cd (a)π ab (c)| = |ac|
in the case x 1 is the neighbour of u 2 and x 3 that of u 4 (see Fig. 4, right). Hence, both functions p and S attain their global minimum at u 1 = u 4 = a, u 2 = u 3 = c, and this remains true for their sum. The case of a rectangle is clear.

Points almost fixing planar convex bodies

In the sense of Baire categories, for most convex bodies K ⊂ R 2 , the inscribed circle C, thought to be the unit circle S 1 of centre 0, is unique and touches bdK in exactly three points a, b, c, with 0 ∈ int abc [START_REF] Zamfirescu | Inscribed and circumscribed circles to convex curves[END_REF]. Then, obviously, the points a, b, c fix K. However, there are convex bodies which cannot be fixed by any set of three points, e.g. parallelograms. A set of points is fixing K if any small move of K brings some point of the set in intK. Precisely, a 1 , . . . , a n fix K if there is a neighbourhood V of the identity id in the set Isom + R 2 of affine rotations such that, for every f ∈ V satisfying f (K) = K, at least one of the a i belongs to intf (K). This is slightly different from another commonly used definition of fixing, e.g. in [START_REF] Bracho | Immobilization of smooth convex figures[END_REF][START_REF] Bracho | Immobilization of solids and mondriga quadratic forms[END_REF], where a subset

H of bdK is said to fix K if id is isolated in the set f ∈ Isom + R 2 ; H ∩ f (intK) = ∅ .
In particular, we consider that a rotation of a disc around its centre does not move the disc.

Observe that both definitions are equivalent if K is not a disc, since in this case there is a neighbourhood V of id in Isom + R 2 such that every f ∈ V \ {id } satisfies f (K) = K. We now introduce the following related notion. The points a 1 , . . . , a n ∈ bdK almost fix the convex body K ⊂ R 2 if, for any neighbourhoods V i of a i (i = 1, . . . , n), there are pairs of points a ′ i , a ′′ i ∈ V i ∩ bdK, such that a ′ 1 , a ′′ 1 , . . . , a ′ n , a ′′ n fix K.

Theorem 4. For any planar convex body K, there are two or three points almost fixing K.

Proof. If K is a disc, then it is obviously almost fixed by two diametrally opposite boundary points. So, assume from now on that K is not a disc. Suppose without loss of generality that C = S 1 is an inscribed circle of K.

Case 1. There exists no a ∈ C ∩ bdK with -a ∈ C ∩ bdK. Let a ∈ C ∩ bdK and A be the component of -a in C ∩ intK. The set A is an open arc a ′ a ′′ ⊂ C of length less than π. Clearly, the triangle aa ′ a ′′ is acute and a, a ′ , a ′′ fix K.

Case 2. There exists a ∈ C ∩ bdK with -a ∈ C ∩ bdK. Let a 1 a 2 ⊂ C be the connected component of a in C ∩ bdK. Then a 1 a 2 = C because K is not a disc. If -a ∈ a 1 a 2 and λ a 1 a 2 > π then K is fixed by a 1 , a 2 and the midpoint a 3 of a 1 a 2 . The case λ a 1 a 2 = π (hence a 1 = ±a and a 2 = ∓a) will be treated later on.

If -a / ∈ a 1 a 2 , let a * 1 a * 2 ⊂ C be the component of -a in C ∩ bdK. Then a 1 a 2 and a * 1 a * 2 are disjoint. Suppose a 1 , a 2 = a or a * 1 , a * 2 = -a, say a * 1 , a * 2 = -a. If λ a * 1 a * 2 < π, then the triangle aa * 1 a * 2 is acute and a, a * 1 , a * 2 fix K. If λ a * 1 a * 2 ≥ π, then λ a 1 a 2 < π. Let m be the midpoint of a 1 a 2 . Since m / ∈ a * 1 a * 2 and λ a * 1 a * 2 ≥ π, we have -m ∈ a * 1 a * 2 .
Then the triangle (-m)a 1 a 2 is acute, and its vertices fix K.

If a 1 = a, a * 1 = -a, and a 1 a 2 , a * 1 a * 2 are non-degenerate and do not lie both on the same half of C, then we are in the already treated case for some point in the relative interior of a 1 a 2 instead of a. It remains the case that at least one of a 1 a 2 , a * 1 a * 2 is degenerate or they lie both on the same half of C. Let the lines Λ ∋ a, -Λ ∋ -a be orthogonal to -aa. Put bc = Λ ∩ bdK, with b, c perhaps not distinct. Take small arcs b ′ b ′′ , c ′ c ′′ , a ′ a ′′ ⊂ bdK containing b, c, -a, respectively, in their relative interior. Then a ′ , a ′′ , b ′ , b ′′ , c ′ , c ′′ fix K, and consequently -a, b, c almost fix K. This remains valid for bc degenerate (b = c); in that case a, -a almost fix K.

In [START_REF] Fruchard | Fixing and almost fixing a convex figure[END_REF], almost necessary and sufficient conditions of first order are given for a finite collection of points to fix K, resp. almost fix K. "Of first order" means that these conditions make use of the left and right tangents of bdK at these points. "Almost" means that the necessary conditions involve large inequalities, whereas the sufficient conditions involve the corresponding strict inequalities. In [START_REF] Bracho | Immobilization of smooth convex figures[END_REF] an almost necessary and sufficient condition of second order, i.e. using the curvature of bdK, is given such that three points fix a C 2 convex body K. We first introduce some notation. Given a planar convex body K, with bdK oriented counterclockwise, and a ∈ bdK, let T ℓ (a), resp. T r (a), be the left, resp. right, tangent at bdK in a. We orient these lines as bdK; thus we have K ⊂ T ℓ (a) + ∩ T r (a) + . Let N ℓ (a), resp. N r (a), be the left and right normals at bdK in a, oriented in the directions T ℓ (a) + , resp. T r (a) + , i.e. the line orthogonal to T ℓ (a), resp. T r (a), containing a, and pointing (as) inward K (as possible). Let L(a) be the open sector, union of the left open half-planes bounded by N ℓ (a) and N r (a):

L(a) = N ℓ (a) + ∪ N r (a) + .
Let L(a) be the corresponding closed sector, and let #» L(a) = {x ∈ S 1 ; a + x ∈ L(a)} be the set of directions of L(a); it is a compact subset of S 1 . Let R(a) and R(a) be the analogous sectors for the right half-planes. Observe that the set of directions of R(a) is -#» L(a), hence will not be needed. If bdK is differentiable at a, then L(a) = R 2 \ R(a), otherwise L(a) ∩ R(a) is the union of two sectors of vertex a. We will also use the intersection sectors:

ℓ(a) = N ℓ (a) + ∩ N r (a) + = R 2 \ R(a), r(a) = R 2 \ L(a)
, their corresponding closed sectors ℓ(a) and r(a), and the set of directions of ℓ(a):

#» ℓ (a) = {x ∈ S 1 ; a + x ∈ ℓ(a)}.
Theorem 5. [START_REF] Fruchard | Fixing and almost fixing a convex figure[END_REF] Let K be a planar convex body and a 1 . . . , a n ∈ bdK.

(i) If a 1 , ..., a n fix K, then both intersections L(a 1 ) ∩ ... ∩ L(a n ) and R(a 1 ) ∩ • • • ∩ R(a n ) are empty. (ii) If the three intersections L(a 1 ) ∩ • • • ∩ L(a n ), R(a 1 ) ∩ • • • ∩ R(a n ), and #» L(a 1 ) ∩ • • • ∩ #» L(a n ) are empty, then a 1 , . . . , a n fix K.
(iii) If a 1 , ..., a n almost fix K, then both intersections ℓ(a 1 ) ∩ ... ∩ ℓ(a n ) and r(a 1 ) ∩ • • • ∩ r(a n ) are empty.

(iv) If the three intersections ℓ(a 2. Another commonly used definition of fixing points is the following one [START_REF] Czyzowicz | Immobilizing a Shape[END_REF]: The points a 1 , . . . , a n ∈ bdK weakly fix K if, for any path γ : [0, 1] → Isom + R 2 , t → γ t such that γ 0 (K) = K and γ 1 (K) = K, there exist i ∈ {1, . . . , n} and t ∈ [0, 1] such that a i ∈ intγ t (K). Obviously, if a 1 , . . . , a n fix K in our first sense, then they weakly fix K. Example 3 of [START_REF] Fruchard | Fixing and almost fixing a convex figure[END_REF] shows that the converse, however, is not true. Nevertherless Theorem 5 remains valid with this notion of weakly fixing. (2)

1 ) ∩ • • • ∩ ℓ(a n ), r(a 1 ) ∩ • • • ∩ r(a n ), and #» ℓ (a 1 ) ∩ • • • ∩ #» ℓ (a n ) are empty,
✘ ✘ ✘ ✘ ✘ ✘ ✘ ✘ ✘ ✘ ✘ ✘ ✘ ✘ ✘ ✘ ✟ ✟ ✟ ✟ r a 0 r c ′ = d = d 0 r b 0 = b = b ′ r c 0 r a r c r ω r a ′ r e ) δ
) α We used here that the length S(a ′ , b 0 , d 0 ) of the Steiner tree joining a ′ , b 0 , and

d 0 is |eb 0 | = 2 + √ 3ε + O(ε 2 )
, where e = (-1 -√ 3ε, 0) is such that a ′ d 0 e is equilateral. As a consequence, (2) is satisfied if ε is small enough.

4 Cages for planar convex bodies in R 3 Let r(K) denote the inradius of the planar convex body K. Theorem 6. For any planar convex body K, L(K) ≥ 6r(K).

Proof. We may suppose r(K) = 1, and B 2 to be inscribed in K. Let G be a cage holding K, and set G 0 = G ∩ affK. Denote by v 1 , . . . , v m the vertices of G, and write w i = π affK (v i ). Take the labelling so that w 1 , . . . , w n are the external vertices of π affK (G).

Case 1. 0 ∈ convG 0 . By the Carathéodory Theorem, there exist a, b, c ∈ G 0 such that 0 ∈ abc. Clearly,

0 ∈ π B 2 (a)π B 2 (b)π B 2 (c),
too. By successively using Theorem 2, Corollary 2.5, and Lemmas 2.3 and 2.6, we obtain

λG ≥ f (w 1 , . . . , w n ) ≥ f (a, b, c) ≥ f (π B 2 (a), π B 2 (b), π B 2 (c)) ≥ 6. Case 2. 0 / ∈ convG 0 . We claim that diamG > 2, yielding the result since G is 3-connected. Consider the arc S 1 ∩ conv({0} ∪ G 0 ), of endpoints α, β. Take a ∈ 0α ∩ G 0 , b ∈ 0β ∩ G 0 ,
and consider the diameter c(-c) of S 1 , parallel to ab. We obtain the trapezoid ab(-c)c. There are two half-lines starting at a and supporting K, one of which, say L a , meets c(-c) at some point a ′ , with c ∈ 0a ′ . Analogously, some supporting half-line

L b of K from b meets c(-c) at b ′ , with -c ∈ 0b ′ . If a -b ≤ 2 then a ′ -b ′ ≥ a -b and K could escape from the cage via conv(L a ∪ L b ∪ K), which contradicts the assumption. Hence, indeed, diamG ≥ diamG 0 ≥ a -b > 2.
The next statement brings a link between points almost fixing a planar convex body and cages holding that body. Then the 1-skeleton of D γ (a ′ a ′′ ab ′ b ′′ b) holds K if γ is close enough to 1, and the length of this cage is arbitrarily close to

|a ′ b ′′ | + |a ′′ b ′ | + | a b| + |a ′ a ′′ | + |a ′′ a| + | aa ′ | + |b ′ b ′′ | + |b ′′ b| + | bb ′ |.
Because this can be done for any a ′ , a We now assume that a, b, c are not collinear. Let d = t(a, b, c) be the Fermat-Torricelli point of a, b, c; we first assume that d is distinct from a, b and c. For any arbitrarily small ε > 0, let a ′ , a ′′ , b ′ , b ′′ , c ′ , c ′′ ∈ relbdK be six points fixing K, labelled in that cyclic order on relbdK, with |aa ′ |, . . . , We now make a dilation P γ = D γ (P ) of P , of centre d and factor γ > 1, γ arbitrarily close to 1. Then, if γ is close enough to 1, the 1-skeleton of P γ is a cage holding K and of length f (a, b, c) + O(ε) γ, hence arbitrarily close to f (a, b, c).

|cc ′′ | < ε. Let a = a ′′ b ′ ∩ c ′′ a ′ . For ε small enough, we have |a a| ≤ |aa ′ | + |a ′ a| ≤ ε + |a ′ a ′′ | sin(∠a ′′ aa ′ ) ≤ 3ε sin(
a ✡ ✡ ✡ ✡ ✡ ✡ ✡ r b ❆ ❆ ❆ ❆ ❆ ❆ ❆ r c ✡ ✡ ✡ ✡ ✡ ✡ ✡ ✡ ❆ ❆ ❆ ❇ ❇ ❇ ❇ r a ′′ ❤ ❤ ❤ r a ′ ✜ ✜ ✜ ✧ ✧ ✧ r a ′′′ ✭ ✭ ✭ ✭ r c ′′ ❅ ❅r c ′′′ ✁ ✁ ✁ rc ′ ✆ ✆ ✆ ✆ ✁ ✁ ✁ r b ′ ❇ ❇ ❇ r b ′′′ ✦ ✦ ✦ r b ′′ ◗ ◗ ◗ r
The case where t(a, b, c) is one of the points, say t(a, b, c) = a, goes similarly: We choose for d the point on the bisector of ∠bac at the distance √ ε from a. The rest of the proof is the same.

We say that the convex body K is weakly strictly convex if it possesses two parallel supporting hyperplanes H, H ′ at distance widK from each other, such that H ∩ K is a single point. A consequence of Theorem 7 is the following.

Corollary 4.2. For any planar weakly strictly convex body K in R 3 , we have L(K) ≤ 3widK.

Proof. Take the two supporting lines H, H ′ given by the definition of weakly strict convexity, and the point {a} = H ∩ K. Then the orthogonal projection b of a onto H ′ belongs to H ′ ∩ K.

With ε > 0 small, consider the two lines parallel to ab and at distance ε from ab. These lines cut relbdK in four points a ′ , a ′′ , b ′ , b ′′ which fix K. This proves that a, b almost fix K and Theorem 7 (i) applies.

An immediate consequence of Corollary 4.2 and Theorem 6 is the following.

Corollary 4.3. Let K be a planar weakly strictly convex body. Assume that K contains a disc of diameter widK. Then we have L(K) = 3widK.

In particular for the unit two-dimensional disc B 2 , we have L(B 2 ) = 6.

Corollary 4.3 also follows from the fact that any cage with S 2 as circumscribed sphere has length more than 6. This was proven by Lillington [START_REF] Lillington | A conjecture for polytopes[END_REF], and generalized to higher dimensions by Linhart [START_REF] Linhart | Kantenlängensumme, mittlere Breite und Umkugelradius konvexer Polytope[END_REF] and further to 1-skeletons of arbitrary convex bodies by Schneider [START_REF] Schneider | On the skeletons of convex bodies[END_REF].

A parallelogram will be called acute if, at each of its vertices, the angles between the diagonal and the sides are acute.

Theorem 8. (i) If T = abc is a triangle of sides I 1 = bc, I 2 = ca, I 3 = ab, then

L(T ) = min{f (x 1 , x 2 , x 3 ) ; x k ∈ I k }.
In particular, for the equilateral triangle T 2 of unit edge length, we have L(T 2 ) = 3+ √ 3

2 . (ii) Let K be a parallelogram of diagonal lengths δ, ∆ with δ ≤ ∆. Then we have L(K) ≥ 3δ. Moreover, if K is acute, then L(K) = 3δ. In particular, for the unit square C 2 , we have

L(C 2 ) = 3 √ 2.
Proof. (i) Since f is continuous and

I 1 × I 2 × I 3 is compact, inf{f (x 1 , x 2 , x 3 ) ; x k ∈ I k } is
reached at some point (u, v, w). Two cases occur: Either each point is in the relative interior of its side, or two points, are at a vertex, say, u = v = c, and the third one w is at the foot of the corresponding height. This second case occurs for all non-acute triangles; it can be seen that it occurs also for some acute ones, if the largest angle is close enough to π 2 . In the first case, the three normals at u, v, w are concurrent by Theorem 3, hence the points u, v, w fix the triangle T . In the second case, we choose u ′ , v ′ arbitrarily close to c such that the three normals at u ′ , v ′ , w are concurrent, and the points u ′ , v ′ , w fix T . This proves that c, w almost fix T . Then Theorem 7 applies, yielding L(T ) ≤ f (u, v, w). Conversely, let G be a cage holding T . Let P = affT and consider the geometric graph π P (G), i.e. the projection of the cage G in the plane P . Let v 1 , . . . v n denote the external vertices of π P (G). In the plane P , let S a denote the half-strip not containing a, bounded by the side bc and the two rays parallel to ab starting from b and from c. Then G intersects S a at some point x, otherwise T would escape from G by a translation inside S a Similarly let S b and S c denote the analogous half-strips for b and c. Then Then G intersects S b at some point y and S c at some point z. Now consider the projections on T : u = π T (x), y = π T (y) and w = π T (z). They satisfy u ∈ I 1 , v ∈ I 2 , and w ∈ I 3 . By respectively using Lemma 2.3, Corollary 2.5, and Theorem 2, we obtain

❳ ❳ ❳ ❳ ❳ ❳ ❳ ❳ ❳ ❳ ❳ ❳ ❳ ❳ ❳ ❳ ❳ ❳ ❳ ❳ ❳ ❳ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ ❆ r r r ✛ r x u ❅ ❅ | r y r v ✄ ✄ ✗ r z r w a b c S a S b S c
f (u, v, w) ≤ f (x, y, z) ≤ f (v 1 , . . . , v n ) ≤ λG.
Lemma 2.7 proves the equality for the equilateral triangle.

(ii) Let G be a cage holding the parallelogram K = abcd, with |ac| = δ ≤ |bd| = ∆, let P = affK, and let v 1 , . . . v n denote the external points of π P (G). In the plane P , let S be the half-strip not containing K determined by da, ab, and bc. Then G intersects S at some point m, otherwise K would escape from G by a translation inside S. Let H be the open half-plane not containing c bounded by the straight line containing a and orthogonal to ac, i.e. H = {x ∈ R 2 ; ∠cax is obtuse }. Since H contains S and since m is in the convex hull of the points v 1 , . . . , v n , one of these points, v k , belongs to H. In the same manner, one v l belongs to the symmetric half-plane H ′ = {x ∈ R 2 ; ∠acx is obtuse }. We then obtain

❍ ❍ ❍ ❍ ❍ ❍ ❍ ❍ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ ✁ r d r y = c ✁ ❍ ✁ ❍ r b r a = x r m r z δ S H H ′
λG ≥ f (v 1 , . . . , v n ) ≥ f (v k , v l ) = 3|v k v l | ≥ 3|ac| = 3δ.
For the 'moreover' part, if K is acute, then the angle ∠dca is acute, hence the vertices a and c almost fix K, giving L(K) = 3δ by Theorem 7 (i). The case of the unit square C 2 is clear.

Remark. In the case of a nonacute parallelogram, it is easy to prove that the vertices a and c do not almost fix K any more and that inf{f (x, y, z) ; x, y, z almost fix K} is attained e.g. for x = a, y = c and z = π da (c), whereas inf{f (x, y) ; x, y almost fix K} is attained only for x = b, y = d and is larger. By Theorem 7 (ii), we then obtain L(K) ≤ f a, c, π da (c) . We conjecture that this is an equality.

5 Cages for convex bodies in R 3

As mentioned in the Introduction, Coxeter's problem from 1959 was completely solved, as follows.

Proposition 5.1. (Besicovitch, Aberth). For the unit ball B 3 , we have

L(B 3 ) = 8π 3 + 2 √ 3.
Denoting the number from the statement of Proposition 5.1 by γ, Besicovitch [START_REF] Besicovitch | A cage to hold a unit-sphere[END_REF] provided a cage G with λG > γ arbitrarily close to γ, while Aberth [START_REF] Aberth | An isoperimetric inequality for polyhedra and its application to an extremal problem[END_REF] proved that λG ≤ γ for no cage G.

Theorem 9. For any K ∈ K, we have L(K) ≤ 2πdiamK. If K is strictly convex, then L(K) ≤ 4(diamK + widK).

Proof. Suppose K ∈ K is strictly convex. Let Π and Π ′ be two parallel supporting planes of K at distance widK from each other, and let a, a ′ be the contact points, respectively. Consider a plane Ψ through a and a ′ , and let K ′ = K ∩ Ψ. Approximate relbdK ′ by a polygon P exterior to and disjoint from K ′ , having two sides α, α ′ parallel to Π, close to a, a ′ respectively. Take a vector v orthogonal to Ψ, and consider the prism Now, among all vertices of convG which are in ∆, choose one x 0 such that the angle between x 0 bc and abc is minimal. Then affx 0 bc separates intT 3 from int convG. Thus, G cannot hold T 3 , the seeked contradiction.

Q v = conv((P + v) ∪ (P -v)). ❜ ❜ ❜ ❜ ❜ ❜ ❜ ❜ ❜ ❜ ✧ ✧ ✧ ✧ ✧ ✧ ✧ ✧ ✧ ✧ r a r b r c Π a Π + a ✥ ✥ ✥ ✥ ✥ ✥ ✭ ✭ ✭ ✭ ✭ ✭ ✭ ✭ ❵ ❵ ❵ ❵ ✚ ✚ ✚ r x r x 0 ✡ ✡ ✡ ✡ ✡ ✡ ✡ ✡ ✡ ✡ ✡ ❇ ❇ ❇ ❇ ❇ ❇ ❇ ❇ ❇ ❇
Theorem 10. For the regular tetrahedron T 3 of unit edge length, we have L(T 3 ) = 3.

Proof. Let T 3 = abcd. A plane parallel and close (at distance η) to ab cuts T 3 along a rectangle R. Any prism P whose 1-skeleton approximates R and is disjoint from T 3 , holds T 3 . As η → 0, the length of six sides of P tends to 0, while the length of each of the remaining three tends to 1. Hence, L(T 3 ) ≤ 3.

Conversely, let G be a cage holding T 3 . If π T 3 (G) does not meet some side e of T 3 , let e ′ denote the side opposite to e; if π T 3 (G) meets all sides, choose opposite e, e ′ arbitrarily. ∈ intC, for i = 1, . . . , 4, otherwise π T 3 (w i ) would be on a face of T 3 instead of the side e i . We have π C (π P (w 1 )) ∈ I 1 , hence π P (w 1 ) is in the closed half-plane bounded by affe 1 and not containing intC. Therefore there exists an external vertex v 1 of π P (G) in the same halfplane, hence also satisfying π C (v 1 ) ∈ I 1 . We do the same with w 2 , w 3 and w 4 . This gives four external vertices v 1 . . . , v 4 of π P (G), with possible coincidences, such that π C (v i ) ∈ I i . By using Theorem 2 and Lemmas 2.3 and 2.8, we then obtain λG ≥ f (v 1 , . . . , v 4 ) ≥ f (π C (v 1 ), . . . , π C (v 4 )) ≥ inf This verifies the bound from the statement.

Compared with the bounds given by Theorem 9, namely 2π for the regular tetrahedron, and 2π √ 3 for the cube, the exact value 3 in Theorem 10 and the bound 4 + 3 √ 2 in Theorem 11 are better. We even dare to formulate the following.

Conjecture. L(C 3 ) = 4 + 3 √ 2.

  , see Proposition 5.1. For the regular simplices of unit edge length, we obtainL(T 2 ) = 3+ √ 3 2

Figure 1 : 2 √ 3 2 √ 3 2 √ 3 2 √ 3

 123232323 Figure 1: The locus O(a, b, k). Left: k ≥ 2 √ 3 |ab|, right: k < 2 √ 3 |ab|.

Figure 3 :

 3 Figure 3: The law of cosines.

3 πFigure 4 :

 34 Figure 4: Left: x 1 is the neighbour of u 4 in the Steiner tree; right: x 1 is the neighbour of u 2 .

1 .

 1 then a 1 , . . . , a n almost fix K. Remarks. The set of directions is needed in items (ii) and (iv): If K = [-2, 2] × [0, 1] then the three points a = (-1, 0), b = (1, 0), c = (0, 1) do not fix K although the intersections L(a) ∩ L(b) ∩ L(c) and R(a) ∩ R(b) ∩ R(c) are empty.

3 .

 3 Example 3.1 below shows that, although every planar convex body can be almost fixed by at most three points, sometimes it may be more economical to use more points to fix it, i.e. it is possible to have inf{f (a, b, c, d) ; a, b, c, d almost fix K} < inf{f (a, b, c) ; a, b, c almost fix K}.

Figure 5 : 1 . 3 . 1 .

 5131 Figure 5: Example 3.1.

Theorem 7 .Question 4 . 1 .Figure 6 :

 7416 Figure 6: A cage holding K in the case (i).

Figure 7 :

 7 Figure 7: If a, b, c are collinear and almost fix K then a, b too.

  ∠cab) and similarly |b b|, |c c| = O(ε). Let #» u be the unit vector orthogonal to Π 0 = affKpointing upward, and put d = d + ε #» u . Consider the tetrahedron T = a b c d. We chop T by three planes Π a , Π b , Π c making an angle of π 4 with Π 0 , with d under them, Π a containing a ′ a ′′ , Π b containing b ′ b ′′ and Π c containing c ′ c ′′ . This gives a heptahedron P , with three triangular faces a′ a ′′ a ′′′ ⊂ Π a , b ′ b ′′ b ′′′ ⊂ Π b , c ′ c ′′ c ′′′ ⊂ Π c , with |aa ′′′ |, |bb ′′′ |, |cc ′′′ | = O(ε), three pentagonal faces da ′′′ a ′′ b ′ b ′′′ , db ′′′ b ′′ c ′ c ′′′ and dc ′′′ c ′′ a ′ a ′′′, and a hexagonal face a ′ a ′′ b ′ b ′′ c ′ c ′′ , see Fig. 8.

  r

Figure 8 :

 8 Figure 8: A cage holding K in the case (ii).

Figure 9 :

 9 Figure 9: Proof of Theorem 8 (i).

Figure 10 :

 10 Figure 10: Proof of Theorem 8 (ii).

Figure 11 :

 11 Figure 11: Proof of Lemma 5.2. Left: top view, right: front view.

4 Figure 12 : 1 √ 2

 41212 Figure 12: Proof of Theorem 10.

u 2 .

 2 i ∈I i f (u 1 , . . . , u 4 ) = 3. Theorem 11. For the cube C 3 of unit edge length, we have L(C 3 ) ≤ 4 + 3 √ Proof. Put C 3 = abcda * b * c * d * , see Fig. 13. Take ε > 0, and let a b ∈ ab and a d ∈ ad be at distance ε 2 from ac. Let L ⊂ affacc * a * be a line outside C 3 , parallel to ac, at distance ε from it. A plane parallel to aa * passing through a b , a d cuts L at a ′ . Let {a * b } = a ′ a b ∩ affa * b * c * d * and {a * d } = a ′ a d ∩ affa * b * c * d * . Analogously, construct c ′ , c * b , c * d . The 1-skeleton S ε of the triangular prism a ′ a * b a * d c ′ c * b c * d immobilises C 3 .

Figure 13 :

 13 Figure 13: Proof of Theorem 11.

  1 , e 2 } is connected, for any pair of external edges e 1 , e 2 ∈ E(G). Let v ∈ V (G) be external, let C be the connected component of v in ∇G, and assume that C = G. Case 1. All external vertices belong to C. Choose w ∈ V (G) \ C. Delete any two external edges; the resulting graph contains a path from w to some external vertex, which therefore does not belong to C, contrary to the present assumption.

	Lemma 2.1. If the geometric graph (G, η) is convex and strongly connected, then ∇G is connected.
	Proof.

Case 2. Some external vertex u does not belong to C. In this case, at least two external edges e 1 , e 2 do not belong to C. Since (G, η) is strongly connected, G \ {e 1 , e 2 } is connected, which yields u ∈ C, and a contradiction is obtained again.

For v small enough, K ∩ skelQ v = ∅. All faces of Q v except (convP ) ± v are rectangles. We chop Q v using planes parallel to these faces, such that the new faces (parallel to the old) now touch K. The number of faces may decrease in the process. The new faces A and A ′ corresponding to the old faces of G v containing α and α ′ lie in Π and Π ′ , respectively. If xy is the line-segment A∩Ψ, then relbdA = x + y + y -x -, where x ± = x ± v, y ± = y ± v. Obviously, xy is parallel to α and contains a. We chop again the already chopped Q v by a plane parallel to xy (but not necessarily to Π), close to A, to replace both edges x + y + and x -y -by edges x * + y * + and x * -y * -touching K. Then, clearly, the new face convx * + y * + y * -x * -cuts K. The same procedure is applied to A ′ . The resulting polytope Q ′ v is not necessarily a prism any more, but skelQ ′ v tightly holds K.

But the polygon P ′ approximates relbdK ′ . Let R be the smallest rectangle in Ψ with two sides in Π, Π ′ , such that convR ⊃ K ′ . This rectangle touches K ′ in a, a ′ and two further points b, b ′ . Two sides of R have length |aa ′ | = widK, the other two have length at most |bb ′ | ≤ diamK. Moreover, convR ⊃ P ′ . Hence, λP ′ ≤ λR ≤ 2(diamK + widK).

Thus, λskelQ ′ v < 4(diamK + widK) + ε, for every ε > 0, proving the second inequality of the statement. The proof of the first inequality of the statement goes similarly, with just three modifications. Instead of starting with the points a, a ′ , we start with the endpoints b, b ′ of a diameter. Then b and b ′ are exposed points of K even if K is not strictly convex. One more modification consists in taking Ψ not arbitrarily through b, b ′ , but containing a third point, interior to K. The third modification concerns λP . It is well-known that K ′ is included in a (planar) convex body

Farther, this leads to the first inequality.

Consider now the regular tetrahedron T 3 = abcd of unit edge length, a cage G holding T 3 , and the projection function π T 3 on T 3 . Lemma 5.2. We have π T 3 (G) ∩ (ab ∪ ac) = ∅.

Proof. Suppose the intersection in the statement is empty. Imagine P 0 := affabc to be horizontal and d above it. Denote by P - 0 the half-space below, i.e. bounded by P 0 and not contaning d. Let Π a be the vertical plane (i.e. orthogonal to affabc) which includes bc. Similarly, let Π b and Π c be the vertical planes which include respectively ac and ab, see Fig 11. Denote by Π + a the half space containing a and bounded by Π a . We have

Since G holds T 3 , G contains a point x below affabc, in the triangular prism ∆ = π -1 T 3 (intabc). We claim that this prism also contains a vertex of G. To see this, take x ∈ G ∩ ∆ to be farthest from Π; this is possible by compactness of G and because the two boundaries of ∆ which are parts of Π b and Π c do not cross G. If x is not a vertex of G, then the side e of G to which x belongs must have an endpoint v below affabc. If v / ∈ Π + , then the other endpoint v ′ of e equals x (otherwise π T 3 (v ′ ) ∈ ab ∪ ac). If v ∈ Π + , then both endpoints v, v ′ of e lie in Π + , and x ∈ {v, v ′ }, or e is parallel to bc and x can be chosen in {v, v ′ }.


Reza Yazdanpanah Abdolmalaki

Xiaolong Liu

Jindong Tan

Modeling and Experimental Study of a Laparoscopic Camera's Interaction with Abdomen Tissue

Materials and Methods:

A mechanical model is proposed to model the bulk abdominal wall tissue by considering four voigt models. The creep experiments were conducted to find the model parameters. Model is validated through creep test on porcine abdomen tissue to represent the real tissue and then implemented in ABAQUS for finite element analysis of the Camera-tissue interaction. A mathematical model is studied to study camera-abdomen tissue interaction. An experiment setup is designed to derive the mechanical properties of porcine abdominal wall tissue. Interaction Experiments were designed to validated the simulations. These interaction forces are the key element in proper control of camera during a laparoscopy surgery.

Conclusions:

The camera system we studied, features pan and linear motion, so these motions were simulated in ABAQUS to find the interaction forces. Comparisons show good compliance between simulation and experiment results. These results were validated by linear and pan motion interaction experiments designed over a bulk porcine abdominal wall. This system will provide the required data for stator's control system for each specific patient during surgery. It also prevents the force overload of tissue and can cancel camera fall during the MIS. In our future work, a closed loop control system will be developed to control camera motion during interaction based on the normal and horizontal contact forces. This system will be used for laparoscopy surgery test on alive pigs.

[1- 5 ]

 5 Results and Discussion: The results of developed model, simulation and experiments are presented in Fig.1: (a) The magnetic controlled insertable camera in contact with abdominal wall; (b) Mechanical model of abdominal wall tissue by four voigt models, representing different layers of tissue; (c) Mathematical model of interaction between cylindrical camera capsule and tissue; (d) Finite Element Model of interaction for linear and rotational camera motions with different velocities; (e) Experimental setup for linear and rotational motion contact forces study on fresh cut porcine tissue; (f) Interaction forces generated during linear motion with different speeds where Comparison shows very good compliance.

Figure 1 .

 1 Figure 1. The top figures show the concept of magnetic controlled insertable cameras and mechanical modeling of the tissue during interaction. The below figures indicate FEM study of interaction and experimental setup to validate the simulation results. The experiments were conducted on porcine tissue and balance setup, with different speeds and contact forces were measured by force sensor.


Reine Lundin

Stefan Lindskog

Entropy of Selectively Encrypted Strings

Keywords: computer security, security measures, selective encryption, entropy

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

The ability to select a security configuration is a feature that has become desirable for low-power mobile devices acting in heterogeneous wireless network environments with limited computing and energy resources. A selective security service is a service that provides various security configuration at run-time to create a trade-off between security and other important parameters such as performance and energy consumption. Selective security is also a way to comply with the principle of adequate security, which states that resources should only be protected to a degree consistent with their value and only until they lose their value.

The concept of selective encryption was introduced in 1995 and 1996 for the purpose of reducing the amount of encrypted MPEG data in a video stream while still providing an acceptable level of confidentiality [START_REF] Spanos | Performance study of a selective encryption scheme for security of networked, real-time video[END_REF]. Selective encryption has also been used to save energy and processing time for H.264/AVC video streams [START_REF] Shahid | Fast protection of H.264/AVC by selective encryption of CABAC for I & P frames[END_REF], JPEG images [START_REF] Podesser | Selective bitplane encryption for secure transmission of image data in mobile environments[END_REF], speech compressed with the G.729 speech encoding standard [START_REF] Su | Hierarchical selective encryption for G.729 speech based on bit sensitivity[END_REF], and a wireless video camera [START_REF] Goodman | Low power scalable encryption for wireless systems[END_REF]. Previous work on selective encryption has mainly focused on performance and/or energy saving issues and on making selectively encrypted information perceptively secure to a certain protection level: that is, to determine which parts of the information to encrypt to distort its perception beyond a desired threshold. In this paper, we continue the investigation in [START_REF] Lundin | Security implications of selective encryption[END_REF] of the confidentiality implications of selective encryption by applying entropy on the generic selective encryption scheme presented in [START_REF] Lindskog | Middleware support for tunable encryption[END_REF]. Using the concept of run-length vector from run-length encoding theory, an expression is derived for entropy of selectively encrypted strings when the number of encrypted substrings, containing one symbol, and the order of the language change.

The remainder of the paper is organized as follows. Sect. 2 introduces terminology and definitions of languages and entropy. Selective encryption is discussed in Sect. 3, and this section also presents the concept of run-length vector from run-length encoding. The expression for entropy of selectively encrypted strings is derived in Sect. 4. Finally, Sect. 5 concludes the paper.

Terminology and Definitions

Terminology and definitions of languages and entropy are introduced in this section.

Languages

In language theory an alphabet Σ is a finite non-empty set of symbols and a string s over Σ is a finite sequence of symbols drawn from that alphabet. The length of a string, |s|, is the number of symbols in the string. If no symbol is drawn from the alphabet, the empty string ǫ is created, having |ǫ| = 0. The concatenation operator | is used to join two strings together by appending. Hence, the string s 1 |s 2 is produced by appending s 2 to s 1 . This is often written as s 1 s 2 without the concatenation operator. Concatenation of a string with the empty string yields the string itself, sǫ = ǫs = s; thus ǫ is the identity string during concatenation.

The set of all strings over an alphabet Σ is called the transitive closure Σ * and every set L ⊂ Σ * is called a language. The size of a language, |L|, is the number of strings in the language. An n-language, L n , is a subset of a language L containing the strings of length n, hence

L n = {s ∈ L; |s| = n} (1)
Note that the union of all n languages constitutes the whole language, hence

L = k n=0 L n ,
where k is an arbitrarily large integer. Furthermore, L 0 = {ǫ} and L 1 = Σ. Thus, L 1 can both refer to a language with strings of length one and the constructing alphabet.

The symbols in a language will normally have different probabilities that depend on preceding symbols. Orders of languages, ω, to approximate the originally language were proposed in [START_REF] Shannon | Claude Elwood Shannon: Collected Papers[END_REF]. The idea is shown in the following list.

L 0 Zero-order language, symbols are independent and uniformly distributed.

L 1 First-order language, symbols are independent and distributed as in L. L 2 Second-order language, symbols are dependent on one preceding symbol with probabilities as in L. L n n-order language, symbols are dependent on n -1 preceding symbols with probabilities as in L.

Entropy

Entropy H(X) [START_REF] Shannon | Claude Elwood Shannon: Collected Papers[END_REF] is a measure that gives the average amount of information of a discrete random variable X. However, entropy can also be seen as a measure giving the average number of guesses in an optimal binary search attack. The discrete random variable X is a variable that attains values from finite sample space X = {x 1 , . . . , x n } with probability distribution

p i = p(X = s i ) = p(X i ).
From this, entropy is defined as follows.

Definition 1. The entropy H(X) of a random variable X with probability distribution p i is defined as

H(X) = - i p i log 2 p i (2)
Definition 1 can be extended to joint and conditional entropy [START_REF] Cover | Elements of Information Theory[END_REF].

Definition 2. The joint entropy H(X 0 , X 1 ) of a pair of random variables (X 0 , X 1 ) with joint probability distribution p ij is defined as

H(X 0 , X 1 ) = - i,j p ij log 2 p ij (3)
Definition 3. The conditional entropy H(X 1 |X 0 ) of the random variable X 1 given the random variable X 0 with conditional probability distribution p j|i is defined as

H(X 1 |X 0 ) = i p i H(X 1 |X i 0 ) = - i,j p ij log 2 p j|i (4)
Definition 2 can be generalized to n random variables that are related in the chain rule as follows.

H(X 0 , . . . , X n-1 ) = H(X 0 ) + n-1 i=1 H(X i |X 0 , . . . , X i-1 ) = n-1 i=0 H i (5)

Selective Encryption

As stated above, the main idea of selective encryption is to create a tradeoff between confidentiality and performance by encrypting chosen substrings of a string while leaving the remaining substrings unencrypted, compressed or encrypted with another encryption algorithm. In this paper, the substrings are assumed to be of equal size, containing one symbol, and the remaining substrings are assumed to be unencrypted and given in position.

The generic selective encryption scheme presented in [START_REF] Lindskog | Middleware support for tunable encryption[END_REF] consists of three basic entities: the string s to be selectively encrypted, the bit vector b that controls which substrings of s to encrypt and the selectively encrypted message E(s). In the scheme, s is divided into n equally sized substrings s i , 0 ≤ i < n, hence

s = n-1 | i=0 s i (6) Furthermore, s i is encrypted if b i mod |b| = 1 and left unencrypted if b i mod |b| = 0.
Without a loss of generality it can be assumed that n = |b|, hence the modulus operator can be removed. The selectively encrypted string E(s) is now constructed as follows.

E(s) = n-1 | i=0 s i if b i = 0 E(s i ) if b i = 1 (7)
From the number of encrypted substrings in E(s), controlled by b, the encryption level is defined as

EL = n-1 i=0 b i n (8)
The concept of run-length vector from run-length encoding theory [START_REF] Cover | Elements of Information Theory[END_REF] is used in this paper in order to capture the distribution of zeros and ones in the bit vector. In run-length encoding, information is stored as a run-length value and a single instance of the corresponding data entity, where a run is the longest substring from the current position containing identical data entities. Thus the description length of information containing long runs will decrease. However, if the information does not contain long runs, the description length of the information might instead increase. The sequence of run-length values of the information is called the run-length vector r. For instance, the bit vector (0, 0, 0, 1, 1, 0, 0) can be written as (302120), with the corresponding run-length vector r = (3, 2, 2). Note how r captures the distribution of runs of zeros and ones in the bit vector. By using the convention of letting the first element in the run-length vector express the run-length of zeros at the beginning of the bit vector, even if there are none, r 2j will then give the run-length of zeros and r 2j+1 will give the run-length of ones in the bit vector. The elements in r will thus alternate between giving the run-lengths of zeros and ones of the bit vector, starting with zeros.

From the notation of the 1-norm [START_REF] Folland | Real Analysis, Modern Techniques and Their Applications[END_REF], also called the taxicab geometry or Manhattan distance, the partial cumulative sum of a vector v will be denoted

||v [k,l] || = l i=k |v i | ( 9
)
where k is the starting position and l the ending position of the vector. Note that

||v [k,l] || = 0 if k > l, and if |v| = n then ||v [0,n-1] || = ||v|| 1 .
From this notation the run-length vector can be calculated from the bit vector as

r i = max{k + 1 ; ||¬ i b [||r [0,i-1] ||,||r [0,i-1] ||+k] || = 0} (10)
where ¬ i is the negation operator to the power of i. In a similar way, the bit vector can be calculated from the run-length vector as

b i = min{k ; ||r [0,k] || > i} mod 2 (11)
The elements in the bit vector will be one when k is an odd integer. By setting α j = ||r [0,2(j-1)] || and β j = ||r [0,2j-1] ||, this will happen for the index sets

I j = [α j , β j ) where J = [1, ⌊ |r| 2 ⌋]. Since I j1 ∩ I j2 = ∅ if j 1 = j 2 ,

the union of all index sets

I = j∈J I j (12)
indexes all ones in the bit vector while still preserving the uniqueness of the indexing.

Confidentiality of Selective Encryption

To investigate how the entropy changes for selectively encrypted strings, let each of the n equally sized substrings of a selectively encrypted string be associated with a random variable as

X 0 , . . . , X n-1 = E(s) = n-1 | i=0 X i = s i if b i = 0 X i = E(s i ) if b i = 1 (13)
Since the entropy is affected only when b i = 1, unencrypted substrings only affect the entropy indirectly; it is sufficient to use the index set I in (12) to describe how entropy changes. Hence, by using ( 5), ( 12) and ( 13), the entropy of selectively encrypted strings can be written as

H ω (X 0 , . . . , X n-1 ) = i∈I H i ω = j∈J i∈Ij H i ω = j∈J H Ij ω = H I ω (14)

Zero-and First-order Languages

The random variables are independent for L 1 languages. Hence, the conditional entropies in ( 14) becomes

H i 1 = H(X i ) ( 15
)
By using (15) in ( 14)

H I 1 = i∈I H(X i ) = |I|H(X 0 ) ( 16
)
where the last step comes from the fact that the random variables are identically distributed. In [START_REF] Lundin | Security implications of selective encryption[END_REF] it was shown for first-order languages that the entropy is given by the expression H(X 0 )

n-1 i=0 b i . However, since |I| = n-1
i=0 b i , the expressions are equal. The symbols are also uniformly distributed for L 0 languages, hence (16) transforms to

H I 0 = |I| log 2 |L 1 0 | (17)
From the derived expression, no confidentiality can be achieved for L 1 or L 0 -languages if the number of encrypted units is zero, |I| = 0, or if the alphabet contains only one symbol, |L 1 | = 1. Furthermore, intuitively and obviously, encrypting more substrings or having a larger alphabet will increase the level of confidentiality. Note also that the entropy tends to infinity as the number of encrypted substrings or the number of symbols in the alphabet tends to infinity.

Second-order Languages

For L 2 languages the probability distribution of the symbols depends on one preceding symbol. Thus, when deriving an expression for H I 2 , the symbol preceding a run of ones must be taken into consideration. In [START_REF] Lundin | Security implications of selective encryption[END_REF], two cases were shown to affect the expression of H I 2 . The first case deals with a run of ones starting at the beginning of the bit vector, i ∈ I 1 = [0, β 1 ), and the second case deals with runs of ones not starting at the beginning of the bit vector, i ∈ I j = [α j , β j ) with α j = 0 and X hj αj -1 . However, a single expression for H I 2 combining the two cases was not derived in the paper.

The conditional entropies in Definition 3 is defined as the average of the entropies of the conditional distributions, averaged over the conditioning distribution. Hence, in the first case, the conditional entropies in (14) can for L 2 languages be written as

H i 2 = p(X 0 , . . . , X l i-1 )H(X i |X l i-1 ) = p(L i-1 2 X l i-1 )H(X i |X l i-1 ) (18)
where p(L i-1 2 X l i-1 ) is a row vector of the second-order probabilities of the strings ending with the substring X l i-1 and H(X i |X l i-1 ) is a column vector of the conditional entropies. By using (18) in ( 14), the expression of the first case becomes

H I1 2 = H(X 0 ) + β1-1 i=1 p(L i-1 2 X l i-1 )H(X i |X l i-1 ) (19)
In the second case, the conditional entropies in (14) can for L 2 languages be written as

H i 2 = p(X αj -1 , . . . , X l i-1 |X hj αj -1 )H(X i |X l i-1 ) = p(L i-αj 2 X l i-1 |X hj αj -1 )H(X i |X l i-1 ) (20)
By using (20) in ( 14), the expression of the second case becomes

H Ij 2 = i∈Ij p(L i-αj 2 X l i-1 |X hj αj -1 )H(X i |X l i-1 ) (21)
If α 1 = 0, then it is only necessary to sum over all I j in (21) to derive H I 2 . However, if α 1 = 0, then (19) needs to be included in the sum. To combine the two cases, the alphabet L 1 must be extended with a new special symbol δ to L 1 = L 1 {δ}. Language L 2 is constructed as an extension to language L 2 by setting p(δ) = 1, p(δ|γ i ) = 0 and ∀γ i ∈ L 1 p(γ i |δ) = p(γ i ). Thus, all strings in L 2 start with the to L 2 independent substring δ and then continue as in L 2 . Now, by setting X h1 -1 = δ, it is possible to rewrite (19) as follows.

H I1 2 = p(X l -1 |X h1 -1 )H(X 0 |X l -1 ) + β1-1 i=1 p(L i-1 2 X l i-1 |X h1 -1 )H(X i |X l i-1 ) = i∈I1 p(L i-α1 2 X l i-1 |X h1 α1-1 )H(X i |X l i-1 ) (22)
Note that ( 22) is a special case of (21) with j = 1, hence

H I 2 = j∈J i∈Ij p(L i-αj 2 X l i-1 |X hj αj -1 )H(X i |X l i-1 ) (23)
For L 1 languages (23) transforms as

H I 2 = j∈J i∈Ij p(L i-αj 1 X i-1 )H(X i ) = i∈I H(X i ) = H I 1 (24)
Furthermore, H I 2 can be larger or smaller than H I 1 . For instance, the probability distribution in Table 1 gives

H I 1 < H I 2 if X 1 0 and H I 2 < H I 1 if X 2 0 .
In Fig. 1 Table 1. The probability distribution that gives

H I 1 < H I 2 if X 1 0 and H I 2 < H I 1 if X 2 0 . pij X 1 1 X 2 1 X 1 0 0.2 0.2 X 2 0 0.2 0.4
the eight different states of a selectively encrypted string containing three substrings are illustrated with encrypted substrings colored gray and unencrypted substrings colored white. The states are grouped into columns according to the encryption level, with arrows pointing towards the next state containing the encrypted substrings of the current state. By using (23) the entropy of the different Fig. 1. The eight states of a selectively encrypted string containing three substrings.

Concluding Remarks

We have in this paper continued the investigation of the confidentiality implications of selective encryption by applying entropy on a generic selective encryption scheme. By using the concept of run-length vector from run-length encoding theory, an expression was derived for entropy of selectively encrypted strings when the number of encrypted substrings, containing one symbol, and the order of the language change.

To further understand the confidentiality implication of selective encryption we will investigate how entropy changes when the substrings are of different sizes larger than one. Moreover, the conditional probabilities in the paper are used left to right. That is, if b = (0, 1), then the first string gives information about the second string. However, if b = (1, 0), then the second string also gives information about the first string. In our future work we will also aim to investigate how the entropy changes for different sources of information and appearances of the bit vector.

Third-order Languages

For L 3 languages, the probability distribution of the symbols depends on the two preceding symbols. Thus, when deriving an expression for H I 3 , two symbols preceding a run of ones must be taken into consideration. Note that it is only the first preceding symbol of a run of ones that is known with certainty to be unencrypted. The second preceding symbol could either be encrypted or unencrypted; this will be denoted

Thus, all strings in L 3 start with the independent substring δ 2 and then continue as in L 3 . The conditional entropies in (14) can now be written for L 3 languages as

Hence,

By using (26), the entropy of the different states in Fig. 1 becomes

n-order Languages

For L n languages the probability distribution of the symbols depends on n -1 preceding symbol. Thus, as before, from the alphabet L 1 = L 1 {δ}, language L n is constructed as an extension of language L n by setting p(δ n-1 ) = 1, p(δ|γ i ) = 0 and ∀γ i ∈ L 1 , p(γ i |δ n-1 ) = p(γ i ) Thus, all strings in L n start with the independent substring δ n-1 and then continue as in L n .

To shorten the notation in the following expressions

and

By using ( 27) and (28) the conditional entropies in (14) can now be written for L n languages as

Hence,