Ugrás a tartalomhoz

Convex Geometry

Csaba Vincze (2013)

University of Debrecen

2.3 The colorful Carathéodory's theorem

2.3 The colorful Carathéodory's theorem

In this section we present a generalization of Carathéodory's theorem due to Imre Bárány [4]. The result was published in 1982 together with further generalizations and applications (see e.g. the cone-version of Carathéodory's theorem and applications to convex functions).

Theorem 2.3.1 Let

 ${H}_{1},\mathrm{\dots },{H}_{n+1}$

be non-empty subsets in the coordinate space of dimension n and suppose that

 $p\in conv{H}_{1}\cap conv{H}_{2}\cap \mathrm{\dots }\cap conv{H}_{n+1}.$

Then there exists elements

 ${v}_{1}\in {H}_{1},\mathrm{\dots },{v}_{n+1}\in {H}_{n+1}$ (2.12)

such that p is in the convex hull of

 ${v}_{1},\mathrm{\dots },{v}_{n+1}.$

Proof Since p is a common element of the convex hulls of the subsets we can suppose, by the classical version of Carathéodory's theorem, that each subset is finite (we can substitute the subset with one of its simplices containing the element p if necessary). Consider the convex hulls of the form

 $C\left({v}_{1},\mathrm{\dots },{v}_{n+1}\right):=conv\left\{{v}_{1},\mathrm{\dots },{v}_{n+1}\right\}$ (2.13)

as each argument runs through the (finitely many) elements of the corresponding subset. Since there are only finitely many convex hulls of type 2.13 we can suppose that

 $C:=C\left({v}_{1},\mathrm{\dots },{v}_{n+1}\right)$

is as close to p as possible. If p is in C then the proof is finished. Suppose that p is not in C and consider a point q in C as close to p as possible. Let D be the open ball centered at p with radius r=d(p,q). The interior of D and C is obviously disjoint; see figure 24. Consider now the tangent hyperplane to the ball at q. Because of theconvexity C and the open half-space containing p must be also disjoint.

Figure 24: Separation: the proof of 3.1.

In what follows we claim that q can be expressed as a convex combination of at most n elements from v(1), ..., v(n+1). If it is an affinely dependent system then the statement is obvious (see Carathéodory's theorem for the reduction of the number of members in the convex combination). Otherwise q can not be in the interior of C because it is the closest point to p from C. Therefore at least one of the elements from v(1), ..., v(n+1) must have a zero coefficient in the convex combination presenting q. Suppose that the first element is missing. Then it can be substituted with any element of the first subset in such a way that the distance between p and the modified convex hull C' is the same as the (minimal) distance between p and C. The last question is how to substitute this element to present a contradiction. Because p is especially in the convex hull of the first subset we can find an element

 ${v}_{1\mathrm{\text{'}}}\in conv{H}_{1}$

in the same open half-space as p. Such a substitution obviously decreases the distance between p and C' as figure 24 shows. This contradicts to the minimality condition. ▮

Remark Image that the points of H(i) have color i. The theorem asserts the existence of the colorful covering simplex

 $S=\left\{{v}_{1},\mathrm{\dots },{v}_{n+1}\right\}$

for the point p. The ''colorful'' means ''containing all colors'' [5]. If

 ${H}_{1}={H}_{2}=...={H}_{n+1}=H$

then we have the classical version of Carathéodory's theorem.