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