Ugrás a tartalomhoz

Convex Geometry

Csaba Vincze (2013)

University of Debrecen

2.2 Carathéodory's theorem

2.2 Carathéodory's theorem

The following theorem belongs to the foundations of the theory of convex sets. It was first proved by Constantin Carathéodory in 1907. In section 1.3 of the previous chapter the convex hull conv H was defined as the collection of convex combinations of the elements from H but we have no any restriction on the number of points of H required to make the combination. Carathéodory's theorem gives a precise answer to the question how to generate the convex hull without unnecessarily repetitions: the number of points of H in the convex combination never has to be more than n+1.

Figure 22: Constantin Carathéodory, 1873-1950.

Theorem 2.2.1 (Carathéodory, Constantin). The convex hull is just the set of convex combinations of affinely independent elements.

Proof Let

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

be a convex combination and suppose that the system v(1), ..., v(k) is affinely dependent. To reduce the number of elements in the convex combination consider the set

Δ : = { ( x 1 , , x k ) | x 1 + + x k = 1 , x 1 0 , , x k 0 }

(2.10)

in the coordinate space of dimension k. The point

λ : = ( λ 1 , , λ k )

is one of its elements. By the affine dependence there exists a non-trivial solution of the following system of equations:

μ 1 v 1 + + μ k v k = 0

and

μ 1 + + μ k = 0 .

Therefore

μ : = ( μ 1 , , μ k )

is a non-zero vector parallel to the hyperplane (the affin hull) of 2.10. Let us start from λ into the direction represented by μ and go as far as we leave 2.10. In terms of the linear algebra choose a non-negative scalar t such that

ν : = λ + t μ

is on the relative boundary[3] of 2.10.

Figure 23: Carathéodory's theorem.

This element involves new coefficients for a convex combination of vectors v(1), ..., v(k) and one of the new coefficients must be zero because of the boundary-condition. Moreover

ν 1 v 1 + + ν k v k = λ 1 v 1 + + λ k v k + t ( μ 1 v 1 + + μ k v k ) =

λ 1 v 1 + + λ k v k = v .

The process can be repeated as far as the system of vectors in the convex combination is affinely dependent. ▮

Theorem 2.2.2 The convex hull of a compact set is compact.

Proof Using Carathéodory theorem the convex hull of the set H in the coordinate space of dimension n is just the image of the set

Δ × H × × H

under the mapping

ϕ ( λ 1 , , λ n , λ n + 1 , v 1 , , v n , v n + 1 ) : = λ 1 v 1 + + λ n v n + λ n + 1 v n + 1 ,

where

Δ : = { ( x 1 , , x n + 1 ) | x 1 + + x n + 1 = 1 , x 1 0 , , x n + 1 0 } .

The Cartesian product of compact sets is obviously compact. So is the convex hull because of the continuity of the mapping Φ. ▮

Definition The convex hull of an affinely independent system of vectors 2.9 is called a simplex of dimension k. The elements of 2.9 are the vertices of the simplex.

It can be easily seen that each point p from the convex hull of a simplex has a unique representation as a convex combination of the vertices. The coefficients in this combination are called the barycentric coordinates of the point p. The element

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

(2.11)

is called the centroid of the simplex.

Corollary 2.2.3 A point p is in conv H if and only if p is in a simplex with vertices from H.

Corollary 2.2.4 The convex hull of a set H in the plane can be considered as the union of convex hulls of at most three points belonging to H. The convex hull of a set H in the space of dimension three can be considered as the union of convex hulls of at most four points belonging to H.