Ugrás a tartalomhoz

Convex Geometry

Csaba Vincze (2013)

University of Debrecen

11. fejezet - Erdős-Vincze's theorem

11. fejezet - Erdős-Vincze's theorem

Let a set of points in the Euclidean plane be given. We are going to investigate the levels of the function measuring the sum of distances from the elements of the point-set which are called focuses. Levels with only one focus are circles. In case of two different points as focuses they are ellipses in the usual sense. If the set of focuses consists of more than two points then we have the so-called polyellipses. In what follows we investigate them from the viewpoint of differential geometry. Lower and upper bounds for the curvature involving explicit constants will be given. They depend on the number of the focuses, the rate of the level and the global minimum of the function measuring the sum of the distances. The minimizer is characterized by E. Vázsonyi (Weiszfeld) [63]. We also present the solution of Weissfeld's problem: any convex closed curve in the plane can be approximated by polyellipses with a sufficiently large number of focuses? The answer is negative as a theorem due to P. Erdős and I. Vincze states. Especially the Hausdorff distances of circumscribed polyellipses from a regular triangle have a positive lower bound. In other words a regular triangle is not an accumulation point of the set of circumscribed polyellipses with respect to the Hausdorff metric.

Figure 68: Weiszfeld Endre, 1916-2003.

Figure 69: Erdős Pál, 1913-1996.

11.1 Polyellipses in the plane

Definition Let p(1), ..., p(n) be not necessarily different points in the coordinate plane and consider the function F defined by the formula

F ( q ) : = i = 1 n d ( q , p i ) .

(11.1)

The levels of the form F(p)=c are called polyellipses with the points p(1), ..., p(n) as focuses. The multiplicity of the focuses means that how many times they appear in the sum 11.1.

Excercise 11.1.1 Prove that the function measuring the sum of distances is convex.

Hint. Use the triangle-inequality to prove the convexity of the function F. The argumentation shows that if the focuses are not collinear then it is a strictly convex function which means that equality

F ( λ p + ( 1 - λ ) q ) = λ F ( p ) + ( 1 - λ ) F ( q )

occurs if and only if the convex combination is trivial. Differentiability is also clear everywhere except the focuses. By the help of the more subtle calculus in section 1.6 we can determine the one-sided directional derivatives at everywhere into any direction: consider the function

f : E 2 R , f ( q ) : = d ( q , p 1 ) ;

then the limit

D v f ( p 1 ) : = l i m t 0 + f ( p 1 + t v ) - f ( p 1 ) t = v

is just the one-sided directional derivative at the the critical point into the direction v. If the point q with coordinates x and y is not critical then the partial derivatives are given by the formulas

D 1 f ( x , y ) = x - x 1 ( x - x 1 ) 2 + ( y - y 1 ) 2 ,

D 2 f ( x , y ) = y - y 1 ( x - x 1 ) 2 + ( y - y 1 ) 2 .

Therefore

D v f ( q ) = 1 d ( q , p 1 ) v , q - p 1

and, consequently,

D v F ( p 1 ) = p j = p 1 v + p j p 1 1 d ( p 1 , p j ) v , p 1 - p j .

In general

D v F ( p i ) = p j = p i v + p j p i 1 d ( p i , p j ) v , p i - p j .

(11.2)

In what follows we characterize the minimizer of the function F by Weiszfeld's theorems (see as geometric median problem). Finding such a point where the global minimum is attained at is crucial in the optimization problems. It is often referred as Fermat-problem according to the original version: how can we find a point in the plane of a triangle for which the sum of distances from the vertices is minimal? The solution of the original problem was given by Evangelista Torricelli. The problem has several types of solutions based on Viviani's theorem, Ptolemy's inequality or mechanical ideas, see e.g. [31] and [54]. For any triangle all of whose angles have less than 120 degree in measure the so-called Fermat-point or isogonic center is the point from which all the sides are seen at the angle having 120 degree in measure. Otherwise the Fermat-point is just the vertex where the critical angle is attained at or, it is exceeded.

Excercise 11.1.2 Using a standard nearest point type argumentation prove the firs obstruction: the minimizer must be in the convex hull of the focal points.

Since the convex hull of finitely many points is obviously compact the first obstruction implies the existence of the global minimizer.

Lemma 11.1.3 If the focal points are not collinear then the minimizer is uniquely determined.

Proof The condition implies that F is a strictly convex function having at most one minimizer. ▮

Excercise 11.1.4 Let four different collinear focal points be given in the plane; prove that any point of the internal segment is a minimizer of thefunction F.

Proposition 11.1.5 (Weiszfeld, Endre) The i-th focal point is a minimizer of the function F if and only if the length of the sum of the normalized position vectors of the rest of focal points with respect to this one is less than or equal to its multiplicity:

t h e   l e n g h t   o f   p j p i 1 d ( p i , p j ) ( p j - p i ) k i .

(11.3)

Proof A necessary and sufficient condition for a point to be the minimizer of a convex function is that the zero vector belongs to the set of the subgradients. According to 11.2 and theorem 1.6.4 it is equivalent to the condition

0 k i + 1 v p j p i 1 d ( p i , p j ) v , p i - p j ,

where k(i) is just the multiplicity of the i-th focal point. Since the right hand side is constant along the rays emanating from the origin, it can be uniquely determined by the help of values along the unit circle. This means that there exists a global minimum of the expression. On the other hand the Cauchy-Schwarz-Buniakowski inequality shows that the minimum is attained if we substitute the vector

v i : = - p j p i 1 d ( p i , p j ) ( p i - p j ) = p j p i 1 d ( p i , p j ) ( p j - p i )

which is just the sum of the normalized position vectors of the rest of focal points with respect to p(i). After substitution we have that the length of v(i) is less or equal than the multiplicity as was to be stated.

Definition A minimizer of the function F is called regular if it doesn't belong to the set of the focal points.

Proposition 11.1.6 (Weiszfeld, Endre) A necessary and sufficientcondition for a point to be a regular minimizer of the function F is that the sum of the normalized position vectors of the focal points with respect to this point is zero.

Proof Let p be a given point in the plane which is not in the set of the focal points. To characterize the minimizer we have the inequality

0 1 v j = 1 n 1 d ( p , p j ) v , p - p j ,

for any non-zero element v. Except from the normalizing factor the right hand side is linear in the variable v which means that the inequality is satisfied for any element v if and only if

0 = i = 1 n 1 d ( p , p j ) ( p - p j )

as was to be proved.

In general there is no any simple way to find the minimizer. Instead of a constructing process we can use algorithms such as the gradient descent method to approximate the global minimum of convex functions on convex domains. To avoid this way we are motivated to estimate directly the minimum value of the function without any information about the exact/approximate position of the minimizer. Letthe number of the focal points be at least two and c* is the minimum of the function F attained at the point p*. For the sake of simplicity we use the notations

c 1 : = F ( p 1 ) , , c n : = F ( p n )

for the values of F at the corresponding focal points, respectively.

Theorem 11.1.7

1 2 c 1 + + c n n - 1 c * c 1 + + c n n ,

(11.4)

Proof The upper bound follows immediately as

c * F ( p 1 + + p n n ) c 1 + + c n n

because of the convexity. For the derivation of the lower bound we use the triangle inequality:

c 1 = d ( p 1 , p 1 ) + j = 2 n d ( p 1 , p j ) = j = 2 n d ( p 1 , p j ) j = 2 n d ( p 1 , p * ) + d ( p * , p j ) =

( n - 1 ) d ( p 1 , p * ) + j = 2 n d ( p * , p j ) = ( n - 2 ) d ( p 1 , p * ) + c *

and a similar result holds for c(2), ..., c(n) too. Taking the sum of these relations we have the lower bound

1 2 c 1 + + c n n - 1 c *

as was to be proved.

Proposition 11.1.8 In case of at least two focuses equality

c * = c 1 + + c n n

holds if and only if the number of different focuses is exactly two, i.e. the levels of the function F are ellipses in the usual sense.

Proof The relation

c * F ( p 1 + + p n n ) c 1 + + c n n

implies that in case of the equality the focuses must be collinear and all of them must be a minimizer. Suppose that we have m different focuses with multiplicities k(1), ..., k(m), respectively. Then

n = k 1 + + k m .

Since the focuses are collinear we can order them in such a way that the points labelled by the first and the last indices are the extreme points of their convex hull. Theorem 11.1.5 shows that

k 1 k 2 + + k m   a n d   k m k 1 + + k m - 1

and, consequently,

k 1 + k m k 1 + k m + ( k 2 + + k m - 1 ) .

Therefore k(2)= ... =k(m - 1)=0. Using Theorem 11.1.5 again it also follows that k(1)=k(m) and, consequently, we have exactly two different focuses with the same multiplicity. This means that the levels are ellipses in the usual sense.

Remark The figure 70 shows how the lower bound can be attained in the non-trivial case of three different collinear focuses. The focuses are

( ± 1,0 ) , ( 0,0 ) .

Figure 70: Ellipses with three collinear focuses in the plane.

Excercise 11.1.9 Find the minimizer of the function F measuring the sum of distances from the vertices of a convex quadrilateral. What about the case of a concave deltoid? Explain how the symmetry about a line helps us finding the minimizer.

Remark Suppose that we have at least three different points as focuses. If they form a regular n-gon then the focal points are invariant under the symmetry group leaving the vertices of the regular n-gon invariant. Since the minimizer is uniquely determined it must be fixed under the elements of the symmetry group.

In what follows we illustrate the problem of parametrization of polyellipses in the plane. Consider the levels of the function F measuring the sum of the distances from the points

p 1 = ( - 1,0 ) , p 2 = ( 0,0 )   a n d   p 3 = ( 1,0 ) .

It can be easily seen that the second focal point is the minimizer with minimal value 2. The figure shows the levels in case of constants 2.5, 3 and 4, respectively. Since the set of the focuses are invariant under the reflections about the coordinate axes it is enough to parameterize the part in the first quadrant of the coordinate plane. Let us introduce the abbreviations

r 1 : = d ( p , p 1 ) , r : = d ( p , p 2 ) , r 3 : = d ( p , p 3 ) ,

where p is an arbitrary point except the origin. In terms of the polar angle α we have the relations

r 1 2 = r 2 + 1 + 2 r c o s α ,

(11.5)

r 3 2 = r 2 + 1 - 2 r c o s α

(11.6)

by the help of using the cosine-rule. If p is a point of the polyellipse defined by the formula

r 1 + r + r 3 = c

then r(1)+r(3)=c - r. According to equations 11.5 and 11.6

4 r c o s α = r 1 2 - r 3 2 = ( r 1 - r 3 ) ( r 1 + r 3 ) = ( r 1 - r 3 ) ( c - r )

and, consequently,

r 1 = r 3 + 4 r c - r c o s α .

Therefore

c = r 1 + r + r 3 = 2 r 3 + 4 r c - r c o s α + r

which implies that

r 3 = 1 2 ( c - r - 4 r c - r c o s α ) .

After substitution into 11.6

r c o s α = c - r 2 r 2 + 1 - ( c - r ) 2 4 .

Using the distance from the origin as the parameter, the function

x ( r ) : = c - r 2 r 2 + 1 - ( c - r ) 2 4

(11.7)

gives the first coordinates of the points of the polyellipse. By the help of Pythagorean theorem

y ( r ) : = 1 - ( c - r ) 2 4 r 2 - ( c - r ) 2 4 .

(11.8)

In order to provide non-negative numbers under the square roots we have to restrict the coordinate functions to the interval

2 3 c 2 - 3 - c 3 r m i n { c - 2 , c 3 } .

Remark Note that c must be greater than the minimum value 2. In case of c=3 the curve contains the focuses p(1) and p(3) as the figure shows.

By the help of standard integral formulas such as

P = a b x ' ( r ) 2 + y ' ( r ) 2 d r

and

A = a b x ( r ) y ' ( r ) d r = - a b x ' ( r ) y ( r ) d r

the perimeter and area of a domain bounded by a parameterized curve can be calculated. The date of the following table are computed by the computer-algebra system MAPLE.

p o l y e l l i p s e s p e r i m e t e r a r e a c = 2.5 2.7123 0.5645 c = 3 4.9604 1.77584 c = 5 7.4968 4.3964

(11.9)