2. Carath´ eodory’s Theorem 7
Figure 2. Example: the polygon B = (−1/2)A can be translated
2. Properties of the Convex Hull. Carath´eodory’s
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
(1 − γ)βi = γ
α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