Ugrás a tartalomhoz

Convex Geometry

Csaba Vincze (2013)

University of Debrecen

3. fejezet - Helly's theorem

3. fejezet - Helly's theorem

Helly's theorem gives a criteria to provide the existence of common elements in each member of a family of convex sets in the space. The one-dimensional version is that if we have a finite collection of intervals and any twoof them have a common point then all of them have a common point. For an alternative formulation image that each interval represents the time that a guest spends at a party. The existence of the common point of each pair of the intervals corresponds to the moment when two guests welcome to each other. It is clear that if x denotes the guest who is the first to leave the party at the moment t(0) then there is no any guest who arrives after t(0) otherwise such a guest can not welcome to x. On the other hand there is no any guest to leave the party before t(0) because x is the first. Therefore t(0) is a moment when all the guests are at the party at.

3.1 Radon's lemma

Lemma 3.1.1 (Radon, Johann). Let D be the set consisting of the elements

v 1 , , v k

in the coordinate space of dimension n. If k is at least n+2 then D can be partitioned into two disjoint subsets such that their convex hulls intersect each other, i.e.

D = D 1 D 2   a n d   D 1 D 2 =

but

c o n v D 1 c o n v D 2 .

Proof Since k is at least n+2 the elements in D are affinely dependent, i.e. we have a non-trivial k-tuple of scalar multipliers such that

λ 1 v 1 + + λ k v k = 0

(3.1)

and λ(1)+ ...+λ(k)=0. Because the sum of the coefficients is zero there must be numbers with different signs among them. For the sake of definiteness suppose that

λ 1 0 , , λ l 0   a n d   λ l + 1 < 0 , , λ k < 0 .

Let

λ : = λ 1 + + λ l = - ( λ l + 1 + + λ k ) > 0

Then, by 3.1

v : = 1 λ ( λ 1 v 1 + + λ k v k ) = - 1 λ ( λ l + 1 v l + 1 + λ k v k )

and the element v is contained in the convex hulls of both

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

as was to be proved. ▮

Figure 25: Johann Radon, 1887-1956.