# Carathéodory's theorem (convex hull)

*See also Carathéodory's theorem (disambiguation) for other meanings*

In convex geometry **Carathéodory's theorem** states that if a point *x* of **R**^{d} lies in the convex hull of a set *P*, there is a subset Template:Italics correction′ of *P* consisting of *d* + 1 or fewer points such that *x* lies in the convex hull of Template:Italics correction′. Equivalently, *x* lies in an *r*-simplex with vertices in *P*, where . The result is named for Constantin Carathéodory, who proved the theorem in 1911 for the case when *P* is compact. In 1914 Ernst Steinitz expanded Carathéodory's theorem for any sets *P* in **R**^{d}.

For example, consider a set *P* = {(0,0), (0,1), (1,0), (1,1)} which is a subset of **R**^{2}. 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)} = Template:Italics correction′, the convex hull of which is a triangle and encloses *x*, and thus the theorem works for this instance, since |Template:Italics correction′| = 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*. Then,

*is a convex combination of a finite number of points in*

**x***P*:

where every **x**_{j} is in *P*, every *λ*_{j} is non-negative, and .

Suppose *k* > *d* + 1 (otherwise, there is nothing to prove). Then, the points **x**_{2} − **x**_{1}, ..., **x**_{k} − **x**_{1} are linearly dependent,

so there are real scalars *μ*_{2}, ..., *μ*_{k}, not all zero, such that

If *μ*_{1} is defined as

then

and not all of the μ_{j} are equal to zero. Therefore, at least one *μ*_{j} > 0. Then,

for any real *α*. In particular, the equality will hold if *α* is defined as

Note that *α*>0, and for every *j* between 1 and *k*,

In particular, *λ*_{i} − *αμ*_{i} = 0 by definition of *α*. Therefore,

where every is nonnegative, their sum is one , and furthermore, . In other words, * x* is represented as a convex combination of at most

*k*-1 points of

*P*. This process can be repeated until

*is represented as a convex combination of at most*

**x***d*+ 1 points in

*P*.

An alternative proof uses Helly's theorem.

## See also

## References

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}.

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}.

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}.

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}

## External links

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