Английская Википедия: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>.Шаблон: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.

The result is named for Constantin Carathéodory, who proved the theorem in 1911 for the case when <math>P</math> is compact. In 1914 Ernst Steinitz expanded Carathéodory's theorem for arbitrary set.

Example

Файл:Caratheodorys theorem example.svg

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

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: Шаблон: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.

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.

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.

Шаблон:AnchorColorful Carathéodory theorem

Let X₁, ..., X_d+1 be sets in R^d 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 = {x₁, ..., x_d+1}, where x₁ ∈ X₁, ..., x_d+1 ∈ X_d+1, such that the convex hull of T contains the point x.

By viewing the sets X₁, ..., X_d+1 as different colors, the set T is made by points of all colors, hence the "colorful" in the theorem's name. The set T is also called a rainbow simplex, since it is a d-dimensional simplex in which each corner has a different color.

This theorem has a variant in which the convex hull is replaced by the conical hull.Шаблон:Rp Let X₁, ..., X_d be sets in R^d 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 = {x₁, ..., x_d}, where x₁ ∈ X₁, ..., x_d ∈ X_d, such that the conical hull of T contains the point x.

Mustafa and Ray extended this colorful theorem from points to convex bodies.

The computational problem of finding the colorful set lies in the intersection of the complexity classes PPAD and PLS.

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

Further reading

• Шаблон:Cite book
• Шаблон:Cite journal

External links

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