Carathéodory's theorem (convex hull)

Carathéodory's theorem (convex hull) Für andere Verwendungen, see Carathéodory's theorem (Begriffsklärung). 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. Nämlich, there is a subset P′ of P consisting of d + 1 or fewer points such that x lies in the convex hull of P′. Äquivalent, x lies in an r-simplex with vertices in P, wo {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.[1] 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.[2] The result is named for Constantin Carathéodory, der den Satz bewiesen hat in 1911 for the case when P is compact.[3] Im 1914 Ernst Steinitz expanded Carathéodory's theorem for any sets P in Rd.[4] Inhalt 1 Beispiel 2 Nachweisen 3 Variants 3.1 Carathéodory's theorem for the conical hull 3.2 Dimensionless variant 3.3 Colorful Carathéodory theorem 4 Siehe auch 5 Anmerkungen 6 Weiterlesen 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, seit |P′| = 3. It may help to visualise Carathéodory's theorem in 2 Maße, 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. Dann, x is a convex combination of a finite number of points in P : {Anzeigestil mathbf {x} = Summe _{j=1}^{k}Lambda _{j}mathbf {x} _{j}} where every xj is in P, every λj is (w.l.o.g.) positiv, und {Anzeigestil Summe _{j=1}^{k}Lambda _{j}=1} .

Suppose k > d + 1 (Andernfalls, es gibt nichts zu beweisen). Dann, the vectors x2 − x1, ..., xk − x1 are linearly dependent, so there are real scalars μ2, ..., μk, not all zero, so dass {Anzeigestil Summe _{j=2}^{k}in _{j}(mathbf {x} _{j}-mathbf {x} _{1})=mathbf {0} .} If μ1 is defined as {displaystyle ihn _{1}:=-sum _{j=2}^{k}in _{j}} dann {Anzeigestil Summe _{j=1}^{k}in _{j}mathbf {x} _{j}=mathbf {0} } {Anzeigestil Summe _{j=1}^{k}in _{j}=0} and not all of the μj are equal to zero. Deswegen, at least one μj > 0. Dann, {Anzeigestil mathbf {x} = Summe _{j=1}^{k}Lambda _{j}mathbf {x} _{j}-alpha sum _{j=1}^{k}in _{j}mathbf {x} _{j}= Summe _{j=1}^{k}(Lambda _{j}-alpha mu _{j})mathbf {x} _{j}} for any real α. Im Speziellen, the equality will hold if α is defined as {Anzeigestil alpha := min _{1leq jleq k}links{{tfrac {Lambda _{j}}{in _{j}}}:in _{j}>0right}={tfrac {Lambda _{ich}}{in _{ich}}}.} Note that α > 0, and for every j between 1 and k, {Anzeigestil Lambda _{j}-alpha mu _{j}geq 0.} Im Speziellen, λi − αμi = 0 by definition of α. Deswegen, {Anzeigestil mathbf {x} = Summe _{j=1}^{k}(Lambda _{j}-alpha mu _{j})mathbf {x} _{j}} where every {Anzeigestil Lambda _{j}-alpha mu _{j}} is nonnegative, their sum is one , and furthermore, {Anzeigestil Lambda _{ich}-alpha mu _{ich}=0} . Mit anderen Worten, 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.[5][6] 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. Nämlich, there is a subset P′ of P consisting of d or fewer points, such that x lies in the conical hull of P′.[7]: 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.[8] 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.[9] 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.