Carathéodory's theorem (convex hull)
lies in the convex hull
can be written as the convex combination of
can be written as the convex combination of at most
An equivalent theorem for conical combinations states that if a point
lies in the conical hull
[2] The result is named for Constantin Carathéodory, who proved the theorem in 1911 for the case when
[3] In 1914 Ernst Steinitz expanded Carathéodory's theorem for arbitrary sets.
[4] 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)} = P′, the convex hull of which is a triangle and encloses x.
is an ordered field, so the theorem and proof works even when
The essence of Carathéodory's theorem is in the finite case.
is the set of finite convex combination of elements of
(see the convex hull page for details).
With the lemma, Carathéodory's theorem is a simple extension: For any
The second part[clarification needed] reduces to the first part by "lifting up one dimension", a common trick used to reduce affine geometry to linear algebra, and reduce convex bodies to convex cones.
is linearly dependent, then we can use induction on its linear span to eliminate one nonzero term in
Then we can interpolate a full interval of representations:
Then we obtain a convex representation of
, define its Carathéodory's number to be the smallest integer
Carathéodory's theorem simply states that any nonempty subset of
This upper bound is not necessarily reached.
has Carathéodory's number equal to 2, since any point inside the sphere is the convex sum of two points on the sphere.
, upper bounds strictly lower than
[8] Recently, Adiprasito, Barany, Mustafa and Terpai proved a variant of Caratheodory's theorem that does not depend on the dimension of the space.
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.
[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.
[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.
[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.
