Ugrás a tartalomhoz

Convex Geometry

Csaba Vincze (2013)

University of Debrecen

3.3 Helly's theorem

3.3 Helly's theorem

Theorem 3.3.1 (E. Helly, 1913). Let B be the collection consisting of convex subsets

B 1 , , B k

in the coordinate space of dimension n. If k is at least n+1 and every subfamily of n+1 sets in B has a non-empty intersection then the family of all sets in B has a non-empty intersection.

Figure 27: Eduard Helly, 1884-1943.

Proof The proof is based on a simple induction. If k=n+1 then the statement is trivial. Suppose that it is true in case of k > n+1 and consider the family consisting of convex subsets

B 1 , , B k , B k + 1 .

(3.10)

We can apply the inductive hypothesis to the reduced family

B ̂ 1 , B 2 , , B k + 1 ,

where the hat - operator deletes its argument. The reduced family obviously heritages the property of non-empty intersections for its subfamilies because they are subfamilies of the extended collection 3.10 too. Then we have an element

v 1 B ̂ 1 B 2 B k + 1 .

In a similar way

v 2 B 1 B ̂ 2 B 3 B k + 1 , , v k + 1 = B 1 B 2 B ̂ k + 1 .

Let D be the set consisting of the elements v(1), ..., v(k+1) and use Radon's lemma 3.1.1 to give a partition D=D(1) U D(2) such that the convex hulls of the sets D(1) and D(2) have a non-empty intersection. For the sake of simplicity suppose that

D 1 = { v 1 , , v l }   a n d   D 2 = { v l + 1 , , v k + 1 } ;

if v is a common element of the convex hulls then we have that

v c o n v D 1 = c o n v { v 1 , , v l } B l + 1 B k + 1

and

v c o n v D 2 = c o n v { v l + 1 , , v k + 1 } B 1 B l .

Therefore v is in the intersection of the sets 3.10 as was to be proved. ▮

Figure 28: Helly's theorem 3.3.1.

The figure illustrates that the sets in Helly's theorem must all be convex. On the other hand if we omit the requirement of finiteness the theorem becomes false as we can see for example in case of the family consisting of the convex sets

B k = ] 0 , 1 k [ × ] 0 , 1 k [ ( k = 1,2 , )

in the coordinate plane with

k = 1 B k = .

The Helly number n+1 cannot be reduced in general: every two sides of a triangle have a point in common, but all the sides do not. The following result due to Victor Klee [36] involves some information about the size of the intersection.

Theorem 3.3.2 (Klee, Victor) Let B be the collection consisting of convex subsets

B 1 , , B k

in the coordinate space of dimension n and suppose that K is a non-empty subset. If k is at least n+1 and for every subfamily of n+1 sets in B there exists a translate of K contained in all n+1 of them then there exists a translate of K contained in all the members of B.

Proof Consider a new collection A of subsets

A i = { p E n | p + K B i } ,

(3.11)

where i=1, ..., k. We are going to prove that A satisfies the conditions of the original Helly's theorem 3.3.1. For the sake of definiteness consider two points p and q belonging to the first member A(1) of the family 3.11:

p + K B 1   a n d   q + K B 1 .

(3.12)

Let λ be a real number between 0 and 1. If v is an element from the set

λ p + ( 1 - λ ) q + K

then it can be written into the form

v = λ p + ( 1 - λ ) q + w = λ ( p + w ) + ( 1 - λ ) ( q + w )

for some w in K. By our hypothesis 3.12

p + w B 1   a n d   q + w B 1

together with their convex combination v. Therefore

λ p + ( 1 - λ ) q A 1

(condition of the convexity). Since for every subfamily of n+1 sets in B there exists a translate of K contained in all n+1 of them, every subfamily of n+1 sets in A has a non-empty intersection. Helly's theorem implies that the family of all sets in A has a non-empty intersection. If p* is one of the common elements then p*+K is contained in all the members of B. ▮

The followingtheorem gives a Helly-type answer to the question how to cover subsets in the space by translates of a given convex set. It will be applied in section 4.2.

Theorem 3.3.3 (Klee, Victor) Let B be the collection consisting of convex subsets

B 1 , , B k

in the coordinate space of dimension n and suppose that K is a non-empty convex subset. If k is at least n+1 and for every subfamily of n+1 sets in B there exists a translate of K containing all n+1 of them then there exists a translate of K containing all the members of B.

Proof Consider a new collection A of subsets

A i = { p E n | B i p + K } ,

(3.13)

where i=1, ..., k. We are going to prove that A satisfies the conditions of the original Helly's theorem 3.3.1. For the sake of definiteness consider two points p and q belonging to the first member A(1) of the family 3.13:

B 1 p + K   a n d   B 1 q + K .

(3.14)

If b(1) is in B(1) then, by our hypothesis 3.14,

b 1 = p + w   a n d   b 1 = q + z

for some elements w and z in K. Let λ be a real number between 0 and 1. Then

b 1 = λ b 1 + ( 1 - λ ) b 1 = λ p + ( 1 - λ ) q + λ w + ( 1 - λ ) z

and the convex combination of w and z is in K because of the convexity. Therefore

b 1 λ p + ( 1 - λ ) q + K

and

λ p + ( 1 - λ ) q A 1

(condition of the convexity). Since for every subfamily of n+1 sets in B there exists a translate of K containing all n+1 of them, every subfamily of n+1 sets in A has a non-empty intersection. Helly's theorem implies that the family of all sets in A has a non-empty intersection. If p* is one of the common elements then p*+K contains all the members of B. ▮

In what follows we present some results to illustrate typical applications of Helly's theorem.

Corollary 3.3.4 Let F be a finite set of points in the coordinate plane. If each triangle formed by the points of F can be covered by a disk with radius r, then F can be covered by a disk with radius r.

Proof Let B be the collection consisting of the closed disks

B 1 , , B k

(3.15)

around the points in F with radius r. Because each triangle formed by the points in F can be covered by a disk with radius r we have a point (the center of the covering disk) having distances from the vertices of the triangle less than or equal to r. Therefore it is a common point of three corresponding disks from the collection B. Using Helly's theorem it follows thatthe family 3.15 has a non-empty intersection. If p* is one of the common elements of B(1), ..., B(k) then the disk around p* with radius r obviously covers the elements of F. ▮

Corollary 3.3.5 (H. Jung). Let F be a finite set of points in the coordinate plane with diameter

d : = m a x { d ( p , q ) | p , q F }   a n d   r : = d / 3 .

Then F can be covered by a disk with radius r.

Proof Because of the previous corollary it is enough to prove that each triangle formed by the points in F can be covered by a disk with radius r. If the points are collinear (degenerate triangles) or they form an obtuse/right triangle then covering disk(s) with radius d/2 can be found. Therefore we discuss only the case of acute triangles.It can be easily seen that there is an angle γ having at least π/3 radian in the measure. Then the radius R of the circumscribed circle can be estimated as

2 R =   t h e   o p p o s i t e   s i d e   s i n γ d s i n ( π / 3 ) R d 3

because the sine function is strictly increasing in the first quadrant. ▮

Remark Note that the upper bound in Jung's theorem is attained in case of a regular triangle.

Corollary 3.3.6 Let F be a finite set containing m points in the coordinate plane. If d is the diameter and

δ : = m i n { d ( p , q ) | p q   a n d   p , q F }

is the minimal distance among the points of F then

d 3 2 ( m - 1 ) δ ,

(3.16)

i.e. the ratio between the longest and the shortest distances can be estimated from below by the square root of the number of elements.

Proof Consider the disks D(1), ..., D(m) around the points of F with radius δ/2. Since the interiors of the disks are pairwise disjoint the area of their union is

A i = 1 m D i = m ( δ / 2 ) 2 π .

(3.17)

Using Jung's theorem 3.3.5 the union of D(1), ..., D(m) can be covered by a disk with radius

R = d / 3 + ( δ / 2 ) m δ / 2 2 π R 2 π .

From the last inequality we have 3.16 immediately. ▮

Corollary 3.3.7 The minimal distance tends to zero under increasing the number of points in a bounded box.