2. Carath´ eodory’s Theorem 7

A

B

A

B

Figure 2. Example: the polygon B = (−1/2)A can be translated

inside A.

2. Properties of the Convex Hull. Carath´eodory’s

Theorem

Recall from (1.2) that the convex hull conv(S) of a set S is the set of all convex

combinations of points from S. Here is our first result.

(2.1) Theorem. Let V be a vector space and let S ⊂ V be a set. Then the convex

hull of S is a convex set and any convex set containing S also contains conv(S).

In other words, conv(S) is the smallest convex set containing S.

Proof. First, we prove that conv(S) is a convex set (cf. Problem 1, Section 1.3).

Indeed, let us choose two convex combinations u = α1u1 + . . . + αmum and v =

β1v1 + . . . + βnvn of points from S. The interval [u, v] consists of the points γu +

(1 − γ)v for 0 ≤ γ ≤ 1. Each such point γα1u1 + . . . + γαmum + (1 − γ)β1v1 + . . . +

(1 − γ)βnvn is a convex combination of points u1,... , um,v1,... , vn from S since

m

i=1

γαi +

n

i=1

(1 − γ)βi = γ

m

i=1

αi + (1 − γ)

n

i=1

βi = γ + (1 − γ) = 1.

Therefore, conv(S) is convex.

Now we prove that for any convex set A such that S ⊂ A, we have conv(S) ⊂ A.

Let us choose a convex combination

u = α1u1 + . . . + αmum

of points u1,... , um from S. We must prove that u ∈ A. Without loss of generality,

we may assume that αi 0 for i = 1, . . . , m. We proceed by induction on m. If