# Carathéodory's theorem (convex hull) Carathéodory's theorem (convex hull) Per altri usi, see Carathéodory's theorem (disambiguazione). An illustration of Carathéodory's theorem for a square in R2 Carathéodory's theorem is a theorem in convex geometry. It states that if a point x of Rd lies in the convex hull of a set P, then x can be written as the convex combination of at most d + 1 points in P. Vale a dire, there is a subset P′ of P consisting of d + 1 or fewer points such that x lies in the convex hull of P′. Equivalentemente, x lies in an r-simplex with vertices in P, dove {displaystyle rleq 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. Note that P need not be itself convex. A consequence of this is that P′ can always be extremal in P, as non-extremal points can be removed from P without changing the membership of x in the convex hull.

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. The result is named for Constantin Carathéodory, che ha dimostrato il teorema in 1911 for the case when P is compact. In 1914 Ernst Steinitz expanded Carathéodory's theorem for any sets P in Rd. Contenuti 1 Esempio 2 Prova 3 Variants 3.1 Carathéodory's theorem for the conical hull 3.2 Dimensionless variant 3.3 Colorful Carathéodory theorem 4 Guarda anche 5 Appunti 6 Ulteriori letture 7 External links Example Consider a set P = {(0,0), (0,1), (1,0), (1,1)} which is a subset of R2. 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, da |P′| = 3. It may help to visualise Carathéodory's theorem in 2 dimensioni, as saying that we can construct a triangle consisting of points from P that encloses any point in P.

Proof Let x be a point in the convex hull of P. Quindi, x is a convex combination of a finite number of points in P : {displaystyle mathbf {X} =somma _{j=1}^{K}lambda _{j}mathbf {X} _{j}} where every xj is in P, every λj is (w.l.o.g.) positivo, e {somma dello stile di visualizzazione _{j=1}^{K}lambda _{j}=1} .

Suppose k > d + 1 (altrimenti, non c'è niente da dimostrare). Quindi, the vectors x2 − x1, ..., xk − x1 are linearly dependent, so there are real scalars μ2, ..., μk, not all zero, tale che {somma dello stile di visualizzazione _{j=2}^{K}in _{j}(mathbf {X} _{j}-mathbf {X} _{1})=mathbf {0} .} If μ1 is defined as {displaystyle lui _{1}:=-sum _{j=2}^{K}in _{j}} poi {somma dello stile di visualizzazione _{j=1}^{K}in _{j}mathbf {X} _{j}=mathbf {0} } {somma dello stile di visualizzazione _{j=1}^{K}in _{j}=0} and not all of the μj are equal to zero. Perciò, at least one μj > 0. Quindi, {displaystyle mathbf {X} =somma _{j=1}^{K}lambda _{j}mathbf {X} _{j}-alpha sum _{j=1}^{K}in _{j}mathbf {X} _{j}=somma _{j=1}^{K}(lambda _{j}-alpha mu _{j})mathbf {X} _{j}} for any real α. In particolare, the equality will hold if α is defined as {displaystyle alfa :=min_{1leq jleq k}sinistra{{tfrac {lambda _{j}}{in _{j}}}:in _{j}>0right}={tfrac {lambda _{io}}{in _{io}}}.} Note that α > 0, and for every j between 1 and k, {displaystyle lambda _{j}-alpha mu _{j}geq 0.} In particolare, λi − αμi = 0 by definition of α. Perciò, {displaystyle mathbf {X} =somma _{j=1}^{K}(lambda _{j}-alpha mu _{j})mathbf {X} _{j}} where every {displaystyle lambda _{j}-alpha mu _{j}} is nonnegative, their sum is one , and furthermore, {displaystyle lambda _{io}-alpha mu _{io}=0} . In altre parole, 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.

Alternative proofs uses Helly's theorem or the Perron–Frobenius theorem. Variants Carathéodory's theorem for the conical hull If a point x of Rd lies in the conical hull of a set P, then x can be written as the conical combination of at most d points in P. Vale a dire, there is a subset P′ of P consisting of d or fewer points, such that x lies in the conical hull of P′.: 257  The proof is similar to the original theorem; the difference is that, in a d-dimensional space, the maximum size of a linearly-independent set is d, while the maximum size of an affinely-independent set is d+1. Dimensionless variant Recently, Adiprasito, Barany, Mustafa and Terpai proved a variant of Caratheodory's theorem that does not depend on the dimension of the space. Colorful Carathéodory theorem Let X1, ..., Xd+1 be sets in Rd and let x be a point contained in the intersection of the convex hulls of all these d+1 sets.