Carathéodory's theorem (convex hull)

For other uses, see Carathéodory's theorem (disambiguation).

An illustration of Carathéodory's theorem for a square in R²

In convex geometry, Carathéodory's theorem states that if a point x of R^d lies in the convex hull of a set P, there is a subset P′ of P consisting of d + 1 or fewer points such that x lies in the convex hull of P′. Equivalently, x lies in an r-simplex with vertices in P, where $r \leq d$ . The smallest r that makes the last statement valid for each x in the convex hull of P is defined as the Carathéodory's number of P. Depending on the properties of P, upper bounds lower than the one provided by Carathéodory's theorem can be obtained.^[1]

The similar theorems of Helly and Radon are closely related to Carathéodory's theorem: the latter theorem can be used to prove the former theorems and vice versa.^[2]

The result is named for Constantin Carathéodory, who proved the theorem in 1907 for the case when P is compact.^[3] In 1914 Ernst Steinitz expanded Carathéodory's theorem for any sets P in R^d.^[4]

Example

Consider a set P = {(0,0), (0,1), (1,0), (1,1)} which is a subset of R². The convex hull of this set is a square. Consider now a point x = (1/4, 1/4), which is in the convex hull of P. We can then construct a set {(0,0),(0,1),(1,0)} = P′, the convex hull of which is a triangle and encloses x, and thus the theorem works for this instance, since |P′| = 3. It may help to visualise Carathéodory's theorem in 2 dimensions, as saying that we can construct a triangle consisting of points from P that encloses any point in P.

Proof of Carathéodory's theorem

Let x be a point in the convex hull of P. Then, x is a convex combination of a finite number of points in P :

\mathbf{x}=\sum_{j=1}^k \lambda_j \mathbf{x}_j

where every x_j is in P, every λ_j is strictly positive, and $\sum_{j=1}^k\lambda_j=1$ .

Suppose k > d + 1 (otherwise, there is nothing to prove). Then, the points x₂ − x₁, ..., x_k − x₁ are linearly dependent,

so there are real scalars μ₂, ..., μ_k, not all zero, such that

\sum_{j=2}^k \mu_j (\mathbf{x}_j-\mathbf{x}_1)=\mathbf{0}.

If μ₁ is defined as

\mu_1:= -\sum_{j=2}^k \mu_j

then

\sum_{j=1}^k \mu_j \mathbf{x}_j=\mathbf{0}

\sum_{j=1}^k \mu_j=0

and not all of the μ_j are equal to zero. Therefore, at least one μ_j > 0. Then,

\mathbf{x} = \sum_{j=1}^k \lambda_j \mathbf{x}_j-\alpha\sum_{j=1}^k \mu_j \mathbf{x}_j = \sum_{j=1}^k (\lambda_j-\alpha\mu_j) \mathbf{x}_j

for any real α. In particular, the equality will hold if α is defined as

\alpha:=\min_{1\leq j \leq k} \left\{ \tfrac{\lambda_j}{\mu_j}:\mu_j>0\right\}=\tfrac{\lambda_i}{\mu_i}.

Note that α > 0, and for every j between 1 and k,

\lambda_j-\alpha\mu_j \geq 0.

In particular, λ_i − αμ_i = 0 by definition of α. Therefore,

\mathbf{x} = \sum_{j=1}^k (\lambda_j-\alpha\mu_j) \mathbf{x}_j

where every $\lambda_j - \alpha \mu_j$ is nonnegative, their sum is one , and furthermore, $\lambda_i-\alpha\mu_i=0$ . In other words, x is represented as a convex combination of at most k-1 points of P. This process can be repeated until x is represented as a convex combination of at most d + 1 points in P.

An alternative proof uses Helly's theorem.^[5]

Notes

↑ Bárány, Imre; Karasev, Roman (2012-07-20). "Notes About the Carathéodory Number". Discrete & Computational Geometry. 48 (3): 783–792. doi:10.1007/s00454-012-9439-z. ISSN 0179-5376.
↑ Danzer et. al. (1963), p.109
↑ Carathéodory, C. "Über den Variabilitätsbereich der Koeffizienten von Potenzreihen, die gegebene Werte nicht annehmen". Mathematische Annalen (in German). 64 (1): 95–115. doi:10.1007/BF01449883. ISSN 0025-5831. MR 1511425.
↑ Steinitz, Ernst (1913), "Bedingt konvergente Reihen und konvexe Systeme", J. Reine Angew. Math., 143 (143): 128–175, doi:10.1515/crll.1913.143.128.
↑ Eggleston, H.G. (1958) pp.40-41

References

Danzer, L.; Grünbaum, B.; Klee, V. (1963), "Helly's theorem and its relatives", Convexity, Proc. Symp. Pure Math., 7, American Mathematical Society, pp. 101–179 .
Eckhoff, J. (1993), "Helly, Radon, and Carathéodory type theorems", Handbook of Convex Geometry, A, B, Amsterdam: North-Holland, pp. 389–448 .
Eggleston, H. G. (1958). Convexity. Cambridge University Press. doi:10.1017/cbo9780511566172.

External links

Concise statement of theorem in terms of convex hulls (at PlanetMath)

This article is issued from Wikipedia - version of the 12/2/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.