Английская Википедия:Carathéodory's theorem (convex hull)
Шаблон:Short description Шаблон:Other uses Carathéodory's theorem is a theorem in convex geometry. It states that if a point <math>x</math> lies in the convex hull <math>\mathrm{Conv}(P)</math> of a set <math>P\subset \R^d</math>, then <math>x</math> can be written as the convex combination of at most <math>d+1</math> points in <math>P</math>. More sharply, <math>x</math> can be written as the convex combination of at most <math>d+1</math> extremal points in <math>P</math>, as non-extremal points can be removed from <math>P</math> without changing the membership of <math>x</math> in the convex hull.
Its equivalent theorem for conical combinations states that if a point <math>x</math> lies in the conical hull <math>\mathrm{Cone}(P)</math> of a set <math>P\subset \R^d</math>, then <math>x</math> can be written as the conical combination of at most <math>d</math> points in <math>P</math>.[1]Шаблон:Rp
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 1911 for the case when <math>P</math> is compact.[3] In 1914 Ernst Steinitz expanded Carathéodory's theorem for arbitrary set.[4]
Example
Carathéodory's theorem in 2 dimensions states that we can construct a triangle consisting of points from P that encloses any point in the convex hull of P.
For example, let P = {(0,0), (0,1), (1,0), (1,1)}. The convex hull of this set is a square. Let x = (1/4, 1/4) in the convex hull of P. We can then construct a set {(0,0),(0,1),(1,0)} = Шаблон:Italics correction′, the convex hull of which is a triangle and encloses x.
Proof
Note: We will only use the fact that <math>\R</math> is an ordered field, so the theorem and proof works even when <math>\R</math> is replaced by any field <math>\mathbb F</math>, together with a total order.
We first formally state Carathéodory's theorem:[5] Шаблон:Math theorem The essence of Carathéodory's theorem is in the finite case. This reduction to the finite case is possible because <math>\mathrm{Conv}(S)</math> is the set of finite convex combination of elements of <math>S</math> (see the convex hull page for details).
Шаблон:Math theoremWith the lemma, Carathéodory's theorem is a simple extension: Шаблон:Math proof
Alternative proofs uses Helly's theorem or the Perron–Frobenius theorem.[6][7]
Variants
Carathéodory's number
For any nonempty <math>P\subset \R^d</math>, define its Carathéodory's number to be the smallest integer <math>r</math>, such that for any <math>x\in \mathrm{Conv}(P)</math>, there exists a representation of <math>x</math> as a convex sum of up to <math>r</math> elements in <math>P</math>.
Carathéodory's theorem simply states that any nonempty subset of <math>\R^d</math> has Carathéodory's number <math>\leq d+1</math>. This upper bound is not necessarily reached. For example, the unit sphere in <math>\R^d</math> has Carathéodory's number equal to 2, since any point inside the sphere is the convex sum of two points on the sphere.
With additional assumptions on <math>P\subset \R^d</math>, upper bounds strictly lower than <math>d+1</math> can be obtained.[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]
Шаблон:AnchorColorful 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]Шаблон:Rp 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
- N-dimensional polyhedron
- Radon's theorem, and its generalization Tverberg's theorem
- Krein–Milman theorem
- Choquet theory
Notes
Further reading
External links
- Concise statement of theorem in terms of convex hulls (at PlanetMath)
Шаблон:Convex analysis and variational analysis
- ↑ Шаблон:Cite Lovasz Plummer
- ↑ Шаблон:Cite conference See in particular p.109
- ↑ Шаблон:Cite journal
- ↑ Шаблон:Cite journal
- ↑ Шаблон:Cite book
- ↑ Шаблон:Cite book See pages 40–41.
- ↑ Шаблон:Cite journal
- ↑ Шаблон:Cite journal
- ↑ Шаблон:Cite arXiv
- ↑ 10,0 10,1 10,2 Шаблон:Cite journal
- ↑ Шаблон:Cite journal
- ↑ 12,0 12,1 Шаблон:Cite journal
- ↑ Шаблон:Citation
- Английская Википедия
- Страницы с неработающими файловыми ссылками
- Articles containing proofs
- Convex hulls
- Geometric transversal theory
- Theorems in convex geometry
- Theorems in discrete geometry
- Страницы, где используется шаблон "Навигационная таблица/Телепорт"
- Страницы с телепортом
- Википедия
- Статья из Википедии
- Статья из Английской Википедии