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
Previous Page Next Page