10 I. Convex Sets at Large
Remark: We prove this in Chapter II; see Corollary II.4.3.
7∗. Prove that a bounded polyhedron P ⊂ Rd is also a polytope.
Remark: We prove this in Chapter IV; see Corollary IV.1.3.
It seems intuitively obvious that in the space of a small dimension, to represent
a given point x from the convex hull of a set A as a convex combination, we would
need to use only a few points of A, although their choice will, of course, depend on
x. For example, in the plane, to represent x as a convex combination, we need to
use only three points; see Figure 4.
Figure 4. Example: to represent u as a convex combination of a, b, c,
d and e, we need only three points, for instance b, e and d.
The general fact is known as Carath´ eodory’s Theorem, which was proved by
C. Carath´ eodory around 1907.
(2.3) Carath´ eodory’s Theorem. Let S ⊂
be a set. Then every point
x ∈ conv(S) can be represented as a convex combination of d + 1 points from
x = α1y1 + . . . + αd+1yd+1, where
αi = 1, αi ≥ 0
and yi ∈ S for i = 1, . . . , d + 1.
Proof. Every point x ∈ conv(S) can be written as a convex combination
x = α1y1 + . . . + αmym
of some points y1,... , ym ∈ S. We can assume that αi 0 for all i = 1, . . . , m. If
m d+1, we can add terms 0y1, say, to get a convex combination with d+1 terms.
Suppose that m d + 1. Let us show that we can construct a convex combination