Ugrás a tartalomhoz

Convex Geometry

Csaba Vincze (2013)

University of Debrecen

11.3 Erdős-Vincze's theorem

11.3 Erdős-Vincze's theorem

The problem whether all the convex plane curves can be arbitrarily approximated by polyellipses under a sufficiently large number of the focuses was posed by Endre Vázsonyi (E. Weiszfeld). In case of a circle we can choose the vertices of (inscribed or circumscribed) regular n-gons as the focuses ofa polyellipses to give an approximating process as n tends to the infinity. Let r be a positive real parameter and consider the polyellipse C(r) determined by the equation

x 2 + ( y + 1 ) 2 + x 2 + ( y - 1 ) 2 + ( x - r ) 2 + y 2 = 2 + r 2 + 1 .

The focuses are

p 1 : = ( 0,1 ) , p 2 : = ( 0 , - 1 ) , p 3 : = ( r , 0 )

and C(r) passes through the points p(1) and p(2). Taking the limit as r tends to the infinity the formula

x 2 + ( y + 1 ) 2 + x 2 + ( y - 1 ) 2 = 2 + x

determines a curve C containing the line segment s(p(1),p(2)).

Figure 74: The limit curve as r tends to the infinity.

Figure 75: Polyellipses with parameters r=5, 15 and 30.

The "limit curve" can be arbitrarily approximated by circumscribed polyellipses with three focuses. More precisely, the Hausdorff distance of the curves goes to being zero as r tends to the infinity. In his paper[24] the authors proved that there is no way to reach a regular triangle by the help of a similar process even if the increase of the number of focuses is allowed. In what follows we present the proof of this theorem using the tools of the differential geometry of plane curves.

Theorem 11.3.1 The approximation of a regular triangle by circumscribed polyellipses always has an absolute error which couldn't be exceededeven if the number of focuses are arbitrary large.

We need some preparation to prove the statement. Let T be a regular triangle in the plane and suppose, in contrary, that there exists a sequence

Ε 1 , , Ε n ,

(11.26)

of circumscribed polyellipses such that

l i m n h ( E n , T ) = 0 .

We use the symbol H for notating the subgroup of isometries which leave the triangle T invariant. H consists of the identity, the reflections about the heights and the rotations around the centre with magnitude (2kπ/3), where k=1 or - 1, respectively. The first step is a kind of symmetrization. Let E be a circumscribed polyellipse defined by the equation

i = 1 n d ( p , p i ) = c

and consider the polyellipse E' such that E' contains all the vertices A, B and C of the triangle and its focal set is

G : = { f ( p i ) | i = 1 , n , f H } .

We are going to prove that

h ( Ε ' , T ) h ( Ε , T ) .

First of all note that the role of the vertices A, B and C are absolutely symmetric as the formulas

f H d ( A , f ( p i ) ) = f H d ( B , f ( p i ) ) = f H d ( C , f ( p i ) )

show. Therefore E' is defined by the equation

f H d ( p , f ( p 1 ) ) + + d ( p , f ( p n ) ) = c ' ,

where (for example)

c ' = f H d ( A , f ( p 1 ) ) + + d ( A , f ( p n ) ) .

Let f be an element in H and consider the polyellipse f(E) with focuses

f ( p 1 ) , , f ( p n )

such that the sum of distances from the focuses is just c. Because T is a subset in E we have that T is a subset in f(E) too. Therefore

d ( A , f ( p 1 ) ) + + d ( A , f ( p n ) ) c .

Since such a formula holds for any f in H we have that c' is less or equal than 6c. Consider now the set

Γ = f H c o n v f ( E ) .

(11.27)

If the point q is not in the union of the convex hulls then

d ( q , f ( p 1 ) ) + + d ( q , f ( p n ) ) > c

for any f in H. Taking the sum as f runs through the elements of H it follows that

f H d ( q , f ( p 1 ) ) + + d ( q , f ( p n ) ) > 6 c c '

and, consequently, q is in the complement of conv E' too. Therefore conv E' (together with T) is a subset of the union 11.27 and E' is not farther from the triangle than the boundary of Γ. On the other hand the boundary of the union 11.27 is not farther from the triangle T than E because[15]

h ( E , T ) = h ( f ( E ) , f ( T ) ) = h ( f ( E ) , T )

(recall that f is an isometry leaving T invariant). This means that E' is not farther from the triangle T than E as was to be proved. In view of the symmetrization process we can suppose that the sequence 11.26 of polyellipses consists of curves passing through all the vertices with an invariant focal set under the elements of the group H. The second step is a process to avoid singularities. Let q(n) be the common point of the perpendicular bisector of the side AB and the arc of E(n) between A and B. Because of the symmetry the line l(n) passing through q(n) into the parallel direction to the side AB supports the polyellipse at q(n). Therefore the Euclidean distance between q(n) and the midpoint M of AB is just the same as the Hausdorff distance between the sets. This means that M is the limit of q(n)'s as n tends to the infinity. From the viewpoint of differential geometry we have two different cases: the point q(n) belongs to the set of the focuses or not. If it does then we ignore this point together with the focuses of the form f(q(n)) as f runs through the elements of the isometry group H of T. In this casewe substitute the polyellipse labelled by n with E'(n) as follows:

(a) the focuses are the rest of those of E(n),

(b) the curve contains all of deleted focuses.

Figure 76: The pair of curves E(n) and E'(n).

Figure 77: Similar triangles.

In what follows we prove that all the vertices of the triangle is in the interior of the convex hull of E'(n); see figure 76 (the focuses are the vertices of a regular hexagon inscribed in the unit circle centered at the origin). Let k(n) be the multiplicity of the point q(n) as the focus of the polyellipse E(n). Then the sum of distances from the focuses of E'(n) must be

c ' n = c n - k n f H d ( q n , f ( q n ) ) = c n - 4 k n ( 1 2 d ( A , B ) + 3 δ n ) ,

where δ(n) is the Euclidean distance between q(n) and M. The formula can be easily derived by the help of using similar triangles 77:

d ( q n , f ( q n ) ) : d ( A , B ) 2 = ( δ n + 1 3 m ) : m 3 ,

where m is the height of the triangle and q(n) is not a fixpoint of f. It happens four times in H. On the other hand

f H d ( A , f ( q n ) ) = 4 a 2 4 + δ n 2 + 2 ( m + δ n ) ,

where ''a'' is the common length of the sides. Therefore

k n f H d ( A , f ( q n ) )

k n ( a 2 + a 2 + a 2 + a 2 + m + m )

4 k n ( a 2 + 3 4 a ) > 4 k n ( a 2 + 3 δ n )

provided that δ(n) is small enough. This means that all the vertices of the triangle is in the interior of the convex hull of E'(n) because

c n - k n f H d ( A , f ( q n ) ) < c n ' .

The comparison of the sum of distances shows that we must have focuses more than the deleted ones provided that n is great enough. In view of the second step we can consider a sequence of polyellipses E(1), ..., E(n), ... such that the focal set is invariant under the elements of the group H and the curvature goes to being zero at the point q(n) as n tends to the infinity: the convexity implies that the curvature radius at q(n) is greater than the radius of the circle passing through the points A, B and q(n). The third step is to prove that the curvature function is uniformly bounded from below which obviously gives a contradiction. Let n be great enough for q=q(n) to be in the interior of the circumscribed circle of the triangle T and consider the function F measuring the sum of distances from the elements of the focal set

G : = { f ( p i ) | i = 1 , n , f H }

of E=E(n).

Lemma 11.3.2 If R is the radius of the circumscribed circle of the triangle then

g r a d F q i = 1 n 24 R R + d ( o , p i ) ,

where o is the center of the triangle, and the set of the focuses is generated from the points

p 1 , , p n

by the symmetry group H.

Proof Recall that the gradient vector is just the sum of the normalized position vectors of q with respect to the focuses:

g r a d F q = f H 1 d ( q , f ( p 1 ) ) ( q - f ( p 1 ) ) + + 1 d ( q , f ( p n ) ) ( q - f ( p n ) ) .

Let k(0) be the multiplicity of the center if it is one of the focuses; otherwise k(0):=0. Then

g r a d F q 6 k 0 + p i o f H 1 d ( q , f ( p i ) ) ( q - f ( p i ) )

because f(o)=o for any element of the symmetry group H. Since the center is the minimizer of any function measuring the sum of distances from the elements of an invariant point-set under H

p i o f H 1 d ( o , f ( p i ) ) ( o - f ( p i ) ) = 0

and we have that the norm of the gradient at the point q is less or equal than

6 k o + p i o f H 1 d ( q , f ( p i ) ) ( q - f ( p i ) ) - 1 d ( o , f ( p i ) ) ( o - f ( p i ) ) .

The estimation

6 k o p i = o 24 R R + d ( p i , o ) = 24 k o

is trivial. From now on we suppose that p(i) is different from the center. In order to estimate the norm of the difference of the unit vectors

v i : = 1 d ( q , f ( p i ) ) ( q - f ( p i ) )

and

w i : = 1 d ( o , f ( p i ) ) ( o - f ( p i ) ) = 1 d ( o , p i ) ( o - f ( p i ) )

consider first of all the case when the i-th focus and all the elements of the form f(p(i)) are in the interior of the circumscribed circle of the triangle. Since the norm of the difference of unit vectors is less or equal than 2 it follows that

4 R R + d ( o , p i ) 2 v i - w i

(11.28)

and, consequently,

f H v i - w i 6 4 R R + d ( o , p i ) = 24 R R + d ( o , p i ) .

The only task is to prove inequality

4 R R + d ( o , p i ) v i - w i

for the focuses outside of the circumscribed circle. From the triangle spanned by the vectors v(i) and w(i) with the same (unit) length we have that

v i - w i = 2 s i n α i 2 2 s i n α i

because the angle α(i) of these unit vectors is obviously less than 90 degree. A simple sine-rule shows that

d ( o , p i ) s i n α i = d ( o , q ) s i n ( f o r   s o m e   a n g l e ) d ( o , q ) R .

Therefore

2 R s i n α i + 2 d ( o , p i ) s i n α i 2 R s i n α i + 2 R 4 R

and, consequently,

2 s i n α i 4 R R + d ( o , p i ) v i - w i 4 R R + d ( o , p i )

as was to be proved. Taking the sum as f runs through the elements of H we have the upper bound for the norm of the gradient vector immediately. ▮

Lemma 11.3.3 If v is a parallel unit vector to the side AB of the triangle then

H e s s F q ( v , v ) 1 2 i = 1 n 1 R + d ( o , p i ) .

Proof Without loss of generality we can suppose that the center of the triangle coincides with the origin and AB is parallel to the y-axis. Then v=(0,1) and the second coordinate of q is zero. Using the formulas for the second order partial derivatives we should estimate the sum of terms of type

S ( q , p i ) : = f H 1 d 3 ( q , f ( p i ) ) ( q 1 - f 1 ( p i ) ) 2

n-times. It is obviously enough to prove that

S ( q , p i ) 1 2 1 R + d ( o , p i )

(11.29)

for any i=1, ..., n. First of all note that the case of p(i)=o is trivial (recall that q lies in the interior of the circumscribed circle and its second coordinate is zero). Suppose that p(i) is different from the origin. By the triangle inequality,

d ( q , f ( p i ) ) d ( q , o ) + d ( o , f ( p i ) ) R + d ( o , p i )

and, consequently,

1 R + d ( o , p i ) f H 1 d 2 ( q , f ( p i ) ) ( q 1 - f 1 ( p i ) ) 2 S ( q , p i ) .

For some isometry f in H, the polar angle of f(p(i)) must be between 120 and 240 (degree). Therefore

1 4 = c o s 2 6 0 1 d 2 ( q , f ( p i ) ) ( q 1 - f 1 ( p i ) ) 2

and it happens at least two times showing that estimation 11.29 holds. ▮

Now we are in the position to finish the proof of the theorem. Using the notations in the proof of the previous lemma the curvature is just

κ ( q ) = 1 g r a d F q H e s s F q ( v , v ) 1 48 R

(11.30)

which is a contradiction.

Remark Inequality 11.30 involves a global minimum for the curvature along the whole arc of the polyellipse because of the symmetry. The method presented in the proof can be used for the estimation of the curvature in all of the cases when the set of the focuses shows invariance under some isometries. This observation yields the general result for the approximation with not necessarily circumscribed polyellipses. If the Hausdorff distance is ε then, by the convexity, the approximating polyellipse must be between the outer and inner ε-parallel bodies of the triangle T. Then we can apply the previous estimation to the curvature of the polyellipse as a circumscribed curve of the inner parallel body. A continuity-type argumentation gives the contradiction.

Figure 78: A continuity-type argumentation.

Excercise 11.3.4 How to generalize Erdős-Vincze's theorem for regular polygons with vertices more than three.