Carathéodory's theorem is a theorem in
convex geometry
In mathematics, convex geometry is the branch of geometry studying convex sets, mainly in Euclidean space. Convex sets occur naturally in many areas: computational geometry, convex analysis, discrete geometry, functional analysis, geometry of numbe ...
. It states that if a point
lies in the
convex hull
In geometry, the convex hull or convex envelope or convex closure of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean space ...
of a set
, then
can be written as the
convex combination
In convex geometry and vector algebra, a convex combination is a linear combination of points (which can be vectors, scalars, or more generally points in an affine space) where all coefficients are non-negative and sum to 1. In other word ...
of at most
points in
. More sharply,
can be written as the convex combination of at most
''extremal'' points in
, as non-extremal points can be removed from
without changing the membership of ''
'' in the convex hull.
Its equivalent theorem for
conical combinations states that if a point
lies in the
conical hull Given a finite number of vectors x_1, x_2, \dots, x_n in a real vector space, a conical combination, conical sum, or weighted sum''Convex Analysis and Minimization Algorithms'' by Jean-Baptiste Hiriart-Urruty, Claude Lemaréchal, 1993, pp. 101, 102 ...
of a set
, then
can be written as the conical combination of at most
points in
.
The similar theorems of
Helly and
Radon
Radon is a chemical element with the symbol Rn and atomic number 86. It is a radioactive, colourless, odourless, tasteless noble gas. It occurs naturally in minute quantities as an intermediate step in the normal radioactive decay chains through ...
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
Constantin Carathéodory ( el, Κωνσταντίνος Καραθεοδωρή, Konstantinos Karatheodori; 13 September 1873 – 2 February 1950) was a Greek mathematician who spent most of his professional career in Germany. He made significant ...
, who proved the theorem in 1911 for the case when
is compact. In 1914
Ernst Steinitz
Ernst Steinitz (13 June 1871 – 29 September 1928) was a German mathematician.
Biography
Steinitz was born in Laurahütte (Siemianowice Śląskie), Silesia, Germany (now in Poland), the son of Sigismund Steinitz, a Jewish coal merchant, and ...
expanded Carathéodory's theorem for arbitrary set.
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'' = . 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 = ′, the convex hull of which is a triangle and encloses ''x.''
Proof
Note: We will only use the fact that
is a
field
Field may refer to:
Expanses of open ground
* Field (agriculture), an area of land used for agricultural purposes
* Airfield, an aerodrome that lacks the infrastructure of an airport
* Battlefield
* Lawn, an area of mowed grass
* Meadow, a grass ...
, so the theorem and proof works even when
is replaced by any field
.
We first formally state Carathéodory's theorem:
The essence of Carathéodory's theorem is in the finite case. This reduction to the finite case is possible because
is the set of ''finite'' convex combination of elements of
(see the
convex hull
In geometry, the convex hull or convex envelope or convex closure of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean space ...
page for details).
With the lemma, Carathéodory's theorem is a simple extension:
Alternative proofs uses
Helly's theorem
Helly's theorem is a basic result in discrete geometry on the intersection of convex sets. It was discovered by Eduard Helly in 1913,. but not published by him until 1923, by which time alternative proofs by and had already appeared. Helly's t ...
or the
Perron–Frobenius theorem
In matrix theory, the Perron–Frobenius theorem, proved by and , asserts that a real square matrix with positive entries has a unique largest real eigenvalue and that the corresponding eigenvector can be chosen to have strictly positive component ...
.
Variants
Carathéodory's number
For any nonempty
, define its Carathéodory's number to be the smallest integer
, such that for any
, there exists a representation of
as a convex sum of up to
elements in
.
Carathéodory's theorem simply states that any nonempty subset of
has Carathéodory's number
. This upper bound is not necessarily reached. For example, the unit sphere in
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
, upper bounds strictly lower than
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.
Colorful Carathéodory theorem
Let ''X''
1, ..., ''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'' = , where ''x''
1 ∈ ''X''
1, ..., ''x''
d+1 ∈ ''X''
d+1, such that the convex hull of ''T'' contains the point ''x''.
By viewing the sets ''X''
1, ..., 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 geometry, a simplex (plural: simplexes or simplices) is a generalization of the notion of a triangle or tetrahedron to arbitrary dimensions. The simplex is so-named because it represents the simplest possible polytope in any given dimension. ...
in which each corner has a different color.
This theorem has a variant in which the convex hull is replaced by the
conical hull Given a finite number of vectors x_1, x_2, \dots, x_n in a real vector space, a conical combination, conical sum, or weighted sum''Convex Analysis and Minimization Algorithms'' by Jean-Baptiste Hiriart-Urruty, Claude Lemaréchal, 1993, pp. 101, 102 ...
.
Let ''X''
1, ..., ''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'' = , where ''x''
1 ∈ ''X''
1, ..., ''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
The Shapley–Folkman lemma is a result in convex geometry that describes the Minkowski addition of sets in a vector space. It is named after mathematicians Lloyd Shapley and Jon Folkman, but was first published by the economist Ros ...
*
Helly's theorem
Helly's theorem is a basic result in discrete geometry on the intersection of convex sets. It was discovered by Eduard Helly in 1913,. but not published by him until 1923, by which time alternative proofs by and had already appeared. Helly's t ...
*
Kirchberger's theorem Kirchberger's theorem is a theorem in discrete geometry, on linear separability. The two-dimensional version of the theorem states that, if a finite set of red and blue points in the Euclidean plane has the property that, for every four points, the ...
*
Radon's theorem
In geometry, Radon's theorem on convex sets, published by Johann Radon in 1921, states that any set of ''d'' + 2 points in R''d'' can be partitioned into two sets whose convex hulls intersect. A point in the intersection of these conve ...
, and its generalization
Tverberg's theorem
In discrete geometry, Tverberg's theorem, first stated by , is the result that sufficiently many points in ''d''-dimensional Euclidean space can be partitioned into subsets with intersecting convex hulls. Specifically, for any set of
:(d + 1)(r ...
*
Krein–Milman theorem
In the mathematical theory of functional analysis, the Krein–Milman theorem is a proposition about compact convex sets in locally convex topological vector spaces (TVSs).
This theorem generalizes to infinite-dimensional spaces and to arbitrar ...
*
Choquet theory In mathematics, Choquet theory, named after Gustave Choquet, is an area of functional analysis and convex analysis concerned with measures which have support on the extreme points of a convex set ''C''. Roughly speaking, every vector of ''C'' sho ...
Notes
Further reading
*
*
External links
Concise statement of theoremin terms of convex hulls (at
PlanetMath
PlanetMath is a free, collaborative, mathematics online encyclopedia. The emphasis is on rigour, openness, pedagogy, real-time content, interlinked content, and also community of about 24,000 people with various maths interests. Intended to be c ...
)
{{DEFAULTSORT:Caratheodory's theorem (convex hull)
Articles containing proofs
Convex hulls
Geometric transversal theory
Theorems in convex geometry
Theorems in discrete geometry