Carathéodory's theorem (convex hull)

Carathéodory's theorem (convex hull) Pour d'autres usages, see Carathéodory's theorem (désambiguïsation). 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. À savoir, there is a subset P′ of P consisting of d + 1 or fewer points such that x lies in the convex hull of P′. De manière équivalente, x lies in an r-simplex with vertices in P, où {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, qui a prouvé le théorème de 1911 for the case when P is compact.[3] Dans 1914 Ernst Steinitz expanded Carathéodory's theorem for any sets P in Rd.[4] Contenu 1 Exemple 2 Preuve 3 Variantes 3.1 Carathéodory's theorem for the conical hull 3.2 Dimensionless variant 3.3 Colorful Carathéodory theorem 4 Voir également 5 Remarques 6 Lectures complémentaires 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, puisque |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 Let x be a point in the convex hull of P. Alors, x is a convex combination of a finite number of points in P : {style d'affichage mathbf {X} =somme _{j=1}^{k}lambda _{j}mathbf {X} _{j}} where every xj is in P, every λj is (w.l.o.g.) positif, et {somme de style d'affichage _{j=1}^{k}lambda _{j}=1} .

Suppose k > d + 1 (Par ailleurs, il n'y a rien à prouver). Alors, the vectors x2 − x1, ..., xk − x1 are linearly dependent, so there are real scalars μ2, ..., μk, not all zero, tel que {somme de style d'affichage _{j=2}^{k}dans _{j}(mathbf {X} _{j}-mathbf {X} _{1})= mathbf {0} .} If μ1 is defined as {style d'affichage lui _{1}:=-sum _{j=2}^{k}dans _{j}} alors {somme de style d'affichage _{j=1}^{k}dans _{j}mathbf {X} _{j}= mathbf {0} } {somme de style d'affichage _{j=1}^{k}dans _{j}=0} and not all of the μj are equal to zero. Par conséquent, at least one μj > 0. Alors, {style d'affichage mathbf {X} =somme _{j=1}^{k}lambda _{j}mathbf {X} _{j}-alpha sum _{j=1}^{k}dans _{j}mathbf {X} _{j}=somme _{j=1}^{k}(lambda _{j}-alpha mu _{j})mathbf {X} _{j}} for any real α. En particulier, the equality will hold if α is defined as {style d'affichage alpha :=min _{1leq jleq k}la gauche{{tfrac {lambda _{j}}{dans _{j}}}:dans _{j}>0right}={tfrac {lambda _{je}}{dans _{je}}}.} Note that α > 0, and for every j between 1 and k, {style d'affichage lambda _{j}-alpha mu _{j}gq 0.} En particulier, λi − αμi = 0 by definition of α. Par conséquent, {style d'affichage mathbf {X} =somme _{j=1}^{k}(lambda _{j}-alpha mu _{j})mathbf {X} _{j}} where every {style d'affichage lambda _{j}-alpha mu _{j}} is nonnegative, their sum is one , and furthermore, {style d'affichage lambda _{je}-alpha mu _{je}=0} . Autrement dit, 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. À savoir, 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.

Then there is a set T = {x1, ..., xd+1}, where x1 ∈ X1, ..., xd+1 ∈ Xd+1, such that the convex hull of T contains the point x.[10] By viewing the sets X1, ..., Xd+1 as different colors, the set T is made by points of all colors, hence the "colorful" in the theorem's name.[11] The set T is also called a rainbow simplex, since it is a d-dimensional simplex in which each corner has a different color.[12] This theorem has a variant in which the convex hull is replaced by the conical hull.[10]: Thm.2.2  Let X1, ..., Xd be sets in Rd and let x be a point contained in the intersection of the conical hulls of all these d sets. Then there is a set T = {x1, ..., xd}, where x1 ∈ X1, ..., xd ∈ Xd, such that the conical hull of T contains the point x.[10] Mustafa and Ray extended this colorful theorem from points to convex bodies.[12] The computational problem of finding the colorful set lies in the intersection of the complexity classes PPAD and PLS.[13] See also Shapley–Folkman lemma Helly's theorem Kirchberger's theorem Radon's theorem, and its generalization Tverberg's theorem Krein–Milman theorem Choquet theory Notes ^ Bárány, Imre; Karasev, Roman (2012-07-20). "Notes About the Carathéodory Number". Discrete & Computational Geometry. 48 (3): 783–792. arXiv:1112.5942. est ce que je:10.1007/s00454-012-9439-z. ISSN 0179-5376. S2CID 9090617. ^ Danzer, L; Grünbaum, B; Klee, V. (1963). "Helly's theorem and its relatives". Convexity. Proc. Symp. Pure Math. Volume. 7. Société mathématique américaine. pp. 101–179. See in particular p.109 ^ Carathéodory, C. (1911). "Über den Variabilitätsbereich der Fourier'schen Konstanten von positiven harmonischen Funktionen". Rendiconti del Circolo Matematico di Palermo (1884–1940) (en allemand). 32 (1): 193–217[see p.200 bottom]. est ce que je:10.1007/BF03014795. S2CID 120032616. ^ Steinitz, Ernst (1913). "Bedingt konvergente Reihen und konvexe Systeme". J. Reine Angew. Math. 1913 (143): 128–175. est ce que je:10.1515/crll.1913.143.128. S2CID 120411668. ^ Eggleston, H. g. (1958). Convexity. la presse de l'Universite de Cambridge. est ce que je:10.1017/cbo9780511566172. ISBN 9780511566172. See pages 40–41. ^ Naszódi, Márton; Polyanskii, Alexandr (2021). "Perron and Frobenius Meet Carathéodory". The Electronic Journal of Combinatorics. 28 (3). arXiv:1901.00540. est ce que je:10.37236/9996. S2CID 119656227. ^ Lovász, László; Plummer, M. ré. (1986). Matching Theory. Annals of Discrete Mathematics. Volume. 29. Hollande du Nord. ISBN 0-444-87916-1. M 0859549. ^ "convex geometry - Caratheodory's theorem for vectors in a cone". Mathematics Stack Exchange. Récupéré 2020-07-22. ^ Adiprasito, Karim; Bárány, Imre; Mustafa, Nabil H.; Terpai, Thomas (2019-08-28). "Theorems of Carathéodory, Helly, and Tverberg without dimension". arXiv:1806.08725 [math.MG]. ^ Sauter à: a b c Bárány, Imre (1982-01-01). "A generalization of carathéodory's theorem". Mathématiques discrètes. 40 (2–3): 141–152. est ce que je:10.1016/0012-365X(82)90115-7. ISSN 0012-365X. ^ Montejano, Louis; Fabila, Ruy; Bracho, Javier; Bárány, Imre; Arocha, Jorge L. (2009-09-01). "Very Colorful Theorems". Discrete & Computational Geometry. 42 (2): 142–154. est ce que je:10.1007/s00454-009-9180-4. ISSN 1432-0444. ^ Sauter à: a b Mustafa, Nabil H.; Rayon, Saurabh (2016-04-06). "An optimal generalization of the Colorful Carathéodory theorem". Mathématiques discrètes. 339 (4): 1300–1305. est ce que je:10.1016/j.disc.2015.11.019. ISSN 0012-365X. ^ Meunier, Frédérique; Mulzer, Wolfgang; Sarrabezolles, Pauline; Stein, Yannik (2017-01-01), "The Rainbow at the End of the Line ? A PPAD Formulation of the Colorful Carathéodory Theorem with Applications", Proceedings of the 2017 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Procédure, Society for Industrial and Applied Mathematics, pp. 1342–1351, est ce que je:10.1137/1.9781611974782.87, récupéré 2022-05-03 Further reading Eckhoff, J. (1993). "Helly, Radon, and Carathéodory type theorems". Handbook of Convex Geometry. Volume. UN, B. Amsterdam: Hollande du Nord. pp. 389–448. Mustafa, Nabil; Meunier, Frédérique; Goaoc, Xavier; De Loera, Jesús (2019). "The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg". Bulletin de l'American Mathematical Society. 56 (3): 415–511. arXiv:1706.05975. est ce que je:10.1090/bull/1653. ISSN 0273-0979. S2CID 32071768. External links Concise statement of theorem in terms of convex hulls (at PlanetMath) Catégories: Theorems in convex geometryConvex hullsGeometric transversal theoryTheorems in discrete geometry

Si vous voulez connaître d'autres articles similaires à Carathéodory's theorem (convex hull) vous pouvez visiter la catégorie Convex hulls.

Laisser un commentaire

Votre adresse email ne sera pas publiée.


Nous utilisons nos propres cookies et ceux de tiers pour améliorer l'expérience utilisateur Plus d'informations