# Carathéodory's theorem (convex hull)

**Carathéodory's theorem (convex hull)** is a result in convex geometry stating that any point in the convex hull of a set in \( \mathbb{R}^d \) can be written as a convex combination of at most \( d+1 \) points of that set, no matter how many points the original combination used. It was first proved by the Greek mathematician [Constantin Carathéodory](https://www.edgepedia.org/constantin-caratheodory) (1873–1950) in 1907 and is regarded as a cornerstone of combinatorial convexity.<sup>[1](https://math.unideb.hu/sites/default/files/upload_documents/convex_geom.pdf)</sup><sup> • </sup><sup>[2](https://www.matem.unam.mx/~roli/investigacion/articulos/Caratheodory-typeTheorems.pdf)</sup>

| Key fact | Detail |
|---|---|
| Statement | Every point of \( \operatorname{conv}(T) \subseteq \mathbb{R}^d \) is a convex combination of at most \( d+1 \) points of \( T \)<sup>[3](https://elliotpaquette.github.io/high-dimensional-probability/lectures/02-convex-hulls.html)</sup> |
| Original publication | C. Carathéodory, "Über den Variabilitätsbereich der Koeffizienten von Potenzreihen...", Math. Ann. 64 (1907), pp. 95–115<sup>[4](https://www.sciencedirect.com/science/article/pii/S0097316500930802)</sup> |
| Proof mechanism | Lift points to \( (t_i, 1) \in \mathbb{R}^{d+1} \); an affine dependence lets one drive a coefficient to zero without changing the represented point, and iterating leaves at most \( d+1 \) points<sup>[3](https://elliotpaquette.github.io/high-dimensional-probability/lectures/02-convex-hulls.html)</sup> |
| Related result | Radon's lemma (1923): any affinely dependent set in \( \mathbb{R}^d \), in particular any \( d+2 \) points, splits into two subsets whose convex hulls intersect<sup>[5](https://page.mi.fu-berlin.de/gmziegler/vorlesung/35discregeom_notes.pdf)</sup> |
| Colorful version | Bárány's colorful Carathéodory theorem, published in 1982: if \( p \) lies in the convex hulls of \( n+1 \) sets \( H_1, \dots, H_{n+1} \), then \( p \) lies in the convex hull of one chosen point from each set<sup>[1](https://math.unideb.hu/sites/default/files/upload_documents/convex_geom.pdf)</sup> |
| Approximate version | A point in a polytope inside the \( \ell_p \) ball of radius \( D \) can be approximated to \( \varepsilon \) in \( \ell_p \) norm by a convex combination of \( O(D^2 p / \varepsilon^2) \) vertices, a bound independent of dimension<sup>[6](https://arxiv.org/abs/1512.08602)</sup> |
| Consequence | The convex hull of a compact set is compact<sup>[7](https://ocw.mit.edu/courses/6-253-convex-analysis-and-optimization-spring-2012/6c63c6219c60378bc27d5b4a9167f1bc_MIT6_253S12_lec_comp.pdf)</sup> |

## Statement

The convex hull of a set \( T \subseteq \mathbb{R}^d \) is the set of all convex combinations \( \sum_{i=1}^m \lambda_i t_i \) with \( t_i \in T \), \( \lambda_i \ge 0 \), and \( \sum_i \lambda_i = 1 \); it is the smallest convex set containing \( T \).<sup>[3](https://elliotpaquette.github.io/high-dimensional-probability/lectures/02-convex-hulls.html)</sup> The definition places no limit on the number \( m \) of terms. Carathéodory's theorem supplies that limit: every point of \( \operatorname{conv}(T) \) is a convex combination of at most \( d+1 \) points of \( T \).<sup>[3](https://elliotpaquette.github.io/high-dimensional-probability/lectures/02-convex-hulls.html)</sup> Equivalently, \( \operatorname{conv}(T) \) is the union of the convex hulls of subsets of \( T \) of size at most \( d+1 \); in the plane this means the hull is a union of hulls of at most three points, and in three-dimensional space of at most four points.<sup>[1](https://math.unideb.hu/sites/default/files/upload_documents/convex_geom.pdf)</sup>

A sharper form says the points can be chosen affinely independent: \( \mathbf{x} \) in the convex hull of \( E \subseteq \mathbb{R}^l \) is a convex combination of affinely independent points of \( E \), and hence of at most \( l+1 \) points.<sup>[8](https://proofwiki.org/wiki/Carath%C3%A9odory%27s_Theorem_%28Convex_Analysis%29)</sup> The bound is tight in general, since an affinely independent set in \( \mathbb{R}^d \) has at most \( d+1 \) members and its vertices cannot be reduced further.<sup>[5](https://page.mi.fu-berlin.de/gmziegler/vorlesung/35discregeom_notes.pdf)</sup>

## Proof idea

The standard proof analyzes a minimal representation. Suppose \( x = \sum_{i=1}^m \lambda_i t_i \) with every \( \lambda_i > 0 \) and \( m > d+1 \). The lifted vectors \( (t_i, 1) \in \mathbb{R}^{d+1} \) are then linearly dependent, so there are coefficients \( a_i \), not all zero, with \( \sum_i a_i t_i = 0 \) and \( \sum_i a_i = 0 \). Replacing each \( \lambda_i \) by \( \lambda_i - s a_i \) leaves both the represented point and the sum of the coefficients unchanged for every \( s \). Choosing the sign of \( (a_i) \) so that some \( a_i > 0 \) and increasing \( s \) until the first coefficient reaches zero eliminates one active point without any coefficient going negative. Iterating this reduction ends with at most \( d+1 \) points.<sup>[3](https://elliotpaquette.github.io/high-dimensional-probability/lectures/02-convex-hulls.html)</sup> The same reduction can be described geometrically: the affine dependence gives a nonzero direction parallel to the simplex of coefficient vectors, and moving along it until the boundary of that simplex is reached forces one coefficient to zero.<sup>[1](https://math.unideb.hu/sites/default/files/upload_documents/convex_geom.pdf)</sup>

The lifting trick connects the convex statement to a conic one. Statements about convex sets translate into statements about cones one dimension up, since \( \operatorname{conv}(S) = \operatorname{slice}(\operatorname{cone}(\operatorname{lift}(S))) \), and a set is affinely dependent exactly when its lift is linearly dependent.<sup>[9](https://kenclarkson.org/cis677/lecture/7/index.html)</sup> The analogous conic theorem says that any nonzero vector in the cone generated by a set in \( \mathbb{R}^n \) is a positive combination of at most \( n \) linearly independent generators.<sup>[7](https://ocw.mit.edu/courses/6-253-convex-analysis-and-optimization-spring-2012/6c63c6219c60378bc27d5b4a9167f1bc_MIT6_253S12_lec_comp.pdf)</sup>

## Immediate consequences

**Compactness of the hull.** If \( X \) is compact, every point of \( \operatorname{conv}(X) \) has a representation \( \sum_{i=1}^{n+1} \alpha_i x_i \) with \( x_i \in X \) and coefficients summing to one. A sequence in the hull therefore gives a bounded sequence of coefficient-and-point tuples, which has a convergent subsequence whose limit again satisfies the defining conditions, so the limit point lies in \( \operatorname{conv}(X) \). This proves that the convex hull of a compact set is compact.<sup>[7](https://ocw.mit.edu/courses/6-253-convex-analysis-and-optimization-spring-2012/6c63c6219c60378bc27d5b4a9167f1bc_MIT6_253S12_lec_comp.pdf)</sup> The same notes record that the convex hull of a closed set need not be closed, so compactness is where the argument genuinely helps.<sup>[7](https://ocw.mit.edu/courses/6-253-convex-analysis-and-optimization-spring-2012/6c63c6219c60378bc27d5b4a9167f1bc_MIT6_253S12_lec_comp.pdf)</sup>

**Separation and the Farkas lemma.** In Clarkson's lecture notes, Carathéodory's theorem enters the proof of the Farkas lemma, the theorem of the alternative underlying linear programming duality: given a set \( S \) and a point \( p \), either \( p \) is in \( \operatorname{cone}(S) \), or there is a linear subspace \( \operatorname{span}(T) \) with \( T \subseteq S \), \( |T| \le \dim(S) - 1 \), and \( T \) linearly independent, separating \( p \) from \( S \). The proof walks through simplicial cones generated by subsets of \( S \), whose sizes are controlled by Carathéodory-type bounds.<sup>[9](https://kenclarkson.org/cis677/lecture/7/index.html)</sup>

**Cubature and subsampling.** Tchakaloff's theorem on cubature formulas, which states that an integral against a measure can be matched exactly by a weighted sum over at most \( d+1 \) support points when integrating \( d \) test functions, is a direct consequence of Carathéodory's theorem applied to the image of the measure under the test-function map.<sup>[10](https://link.springer.com/article/10.1007/s13160-020-00451-x)</sup> The related Carathéodory–Tchakaloff subsampling method compresses a discrete measure supported on a large finite set \( F \) to one supported on a subset \( G \subseteq F \) with \( |G| \le d \), matching the same integrals; it is computed as a basic feasible solution of a linear program with a trivial objective.<sup>[10](https://link.springer.com/article/10.1007/s13160-020-00451-x)</sup>

## The colorful version

Imre Bárány, a Hungarian mathematician working in combinatorial geometry, published the colorful Carathéodory theorem in 1982. It concerns \( n+1 \) non-empty sets \( H_1, \dots, H_{n+1} \) in \( \mathbb{R}^n \) whose convex hulls share a point \( p \); the conclusion is that \( p \) lies in the convex hull of a transversal, one point \( v_i \) chosen from each \( H_i \).<sup>[1](https://math.unideb.hu/sites/default/files/upload_documents/convex_geom.pdf)</sup> The proof reduces each \( H_i \) to a finite simplex containing \( p \), then takes a convex hull \( C \) of a transversal closest to \( p \) and shows that if \( p \notin C \), a substitution using a point of \( \operatorname{conv} H_1 \) on \( p \)'s side of a separating hyperplane decreases the distance, contradicting minimality.<sup>[1](https://math.unideb.hu/sites/default/files/upload_documents/convex_geom.pdf)</sup> Later work generalized the statement further, including a 2016 version of Holmsen in which a matroid constrains the admissible transversals, and cone and constrained variants.<sup>[11](https://arxiv.org/abs/2607.06172)</sup>

## Approximate and no-dimensional variants

**Approximate Carathéodory.** The exact bound \( d+1 \) depends on the ambient dimension, which is costly in high dimension; in a million-dimensional space a representation using a million points may not feel sparse.<sup>[3](https://elliotpaquette.github.io/high-dimensional-probability/lectures/02-convex-hulls.html)</sup> The approximate theorem trades exactness for a dimension-free count: given a polytope \( P \) inside the \( \ell_p \) ball of radius \( D \) and a point \( u \in P \), a convex combination of \( O(D^2 p / \varepsilon^2) \) vertices approximates \( u \) to within \( \varepsilon \) in \( \ell_p \) norm for \( p \ge 2 \), and this bound is tight.<sup>[6](https://arxiv.org/abs/1512.08602)</sup> The result is an incarnation of Maurey's lemma in functional analysis, and constructive nearly-linear-time algorithms follow from mirror descent on a dual convex function obtained via Sion's theorem.<sup>[6](https://arxiv.org/abs/1512.08602)</sup> A simpler probabilistic proof shows that an average of \( m = \lceil R^2 / \varepsilon^2 \rceil \) sampled points of \( T \) approximates any hull point within \( \varepsilon \).<sup>[3](https://elliotpaquette.github.io/high-dimensional-probability/lectures/02-convex-hulls.html)</sup>

Siddharth Barman, a researcher in algorithmic game theory, used an \( \ell_p \)-version of the approximate theorem, with the sparsity bound \( b \) depending on \( \varepsilon \) and \( p \) but not on the dimension \( d \), to compute \( \varepsilon \)-Nash equilibria of bimatrix games with sparse aggregate payoff matrices in time \( n^{O(\log s / \varepsilon^2)} \) when each column of \( A+B \) has at most \( s \) nonzero entries, and to obtain algorithms for dense subgraph problems.<sup>[12](https://epubs.siam.org/doi/10.1137/15M1050574)</sup>

**No-dimensional versions.** A different relaxation keeps exactness but drops the dependence on \( d \) in a metric sense: given an \( n \)-element set \( P \) in [Euclidean space](https://www.edgepedia.org/euclidean-space), a point \( a \in \operatorname{conv} P \), and an integer \( r \le n \), there is a subset \( Q \subseteq P \) of \( r \) elements such that the distance from \( a \) to \( \operatorname{conv} Q \) is less than \( \operatorname{diam} P / \sqrt{2r} \).<sup>[13](https://arxiv.org/abs/1806.08725)</sup> Work on the Carathéodory number, the minimal number of points needed per hull point for a particular set, gives sufficient conditions for a compactum in \( \mathbb{R}^n \) to have Carathéodory number below \( n+1 \), generalizing an older result of Fenchel.<sup>[14](https://arxiv.org/abs/1112.5942)</sup> In the plane, refinements proved in 1929 by Moritz Werner Fenchel (1905–1988), a Danish mathematician of German origin, and in 1934 by the Dutch mathematician Lucas Nicolaas Hendrik Bunt (1905–1984), show that if \( D \) has at most two connected components, every point of \( \operatorname{conv} D \) is a convex combination of just two points of \( D \).<sup>[15](https://tangente-mag.com/en/articles/convex-sets-and-line-segments)</sup>

## Context among classical convexity theorems

Carathéodory's theorem stands alongside Helly's theorem and Radon's theorem at the origin of combinatorial geometry of convex sets. Helly's theorem says that a finite family of convex sets in \( \mathbb{R}^d \), or a family of compact convex sets, has a common point whenever every \( d+1 \) or fewer members do; Radon's theorem says any set of \( d+2 \) or more points in \( \mathbb{R}^d \) contains two disjoint subsets whose convex hulls intersect.<sup>[16](https://www.sciencedirect.com/science/article/abs/pii/B9780444895967500171)</sup> The three results are interderivable, and Radon's lemma is a standard route to Carathéodory's theorem.<sup>[5](https://page.mi.fu-berlin.de/gmziegler/vorlesung/35discregeom_notes.pdf)</sup> The theorem also fails outside finite dimensions: the \( d+1 \) bound relies on the dimension being finite, and counterexamples exist in infinite-dimensional spaces.<sup>[17](https://math.stackexchange.com/questions/1009920/finding-a-counter-example-to-caratheodorys-convex-hull-theorem-for-infinite-dim)</sup>

## References

1. [Chapter 2, Carathéodory's theorem, lecture notes on convex geometry, University of Debrecen](https://math.unideb.hu/sites/default/files/upload_documents/convex_geom.pdf)
2. [Bokowski, Bracho, Strausz. Carathéodory-type theorems. Discrete & Computational Geometry 45 (2011), 261–271](https://www.matem.unam.mx/~roli/investigacion/articulos/Caratheodory-typeTheorems.pdf)
3. [Lecture 2: Convex Hulls and Sparse Approximation, High-Dimensional Probability (Paquette)](https://elliotpaquette.github.io/high-dimensional-probability/lectures/02-convex-hulls.html)
4. [Carathéodory's Theorem and H-Convexity, Journal of Combinatorial Theory Series A](https://www.sciencedirect.com/science/article/pii/S0097316500930802)
5. [Combinatorial convexity, lecture notes, Freie Universität Berlin (Ziegler)](https://page.mi.fu-berlin.de/gmziegler/vorlesung/35discregeom_notes.pdf)
6. [Tight Bounds for Approximate Carathéodory and Beyond, arXiv:1512.08602](https://arxiv.org/abs/1512.08602)
7. [6.253 Convex Analysis and Optimization, complete lecture notes, MIT OpenCourseWare](https://ocw.mit.edu/courses/6-253-convex-analysis-and-optimization-spring-2012/6c63c6219c60378bc27d5b4a9167f1bc_MIT6_253S12_lec_comp.pdf)
8. [Carathéodory's Theorem (Convex Analysis), ProofWiki](https://proofwiki.org/wiki/Carath%C3%A9odory%27s_Theorem_%28Convex_Analysis%29)
9. [CIS677 Notes for lecture 7: Convexity (K. Clarkson)](https://kenclarkson.org/cis677/lecture/7/index.html)
10. [Monte Carlo cubature construction, Japan Journal of Industrial and Applied Mathematics (2020)](https://link.springer.com/article/10.1007/s13160-020-00451-x)
11. [Cone and constrained colorful Carathéodory Theorems, arXiv:2607.06172](https://arxiv.org/abs/2607.06172)
12. [Barman, S. Approximating Nash Equilibria and Dense Subgraphs via an Approximate Version of Carathéodory's Theorem. SIAM Journal on Computing](https://epubs.siam.org/doi/10.1137/15M1050574)
13. [Theorems of Carathéodory, Helly, and Tverberg without dimension, arXiv:1806.08725](https://arxiv.org/abs/1806.08725)
14. [Bárány, I., Karasev, R. Notes about the Caratheodory number, arXiv:1112.5942](https://arxiv.org/abs/1112.5942)
15. [Convex sets and line segments, Tangente Magazine](https://tangente-mag.com/en/articles/convex-sets-and-line-segments)
16. [Eckhoff, J. Helly, Radon, and Carathéodory Type Theorems. Handbook of Convex Geometry (1993), 389–448](https://www.sciencedirect.com/science/article/abs/pii/B9780444895967500171)
17. [Counter example to Carathéodory's convex hull theorem for infinite-dimensional space, Mathematics Stack Exchange](https://math.stackexchange.com/questions/1009920/finding-a-counter-example-to-caratheodorys-convex-hull-theorem-for-infinite-dim)

---
*Topic: Encyclopedia › Physical world and mathematics › Mathematics and statistics › Geometry and topology › Metric, convex, and discrete geometry*

*Initially written Sep 17, 2026 · Reviewed: Sep 30, 2026; Oct 15, 2026 · Edited: Sep 30, 2026; Oct 15, 2026 · Last review: Oct 15, 2026*

*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*

License: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license