Carathéodory's theorem (convex hull)
Carathéodory's theorem is a theorem in convex geometry. It states that if a point [math]\displaystyle{ x }[/math] lies in the convex hull [math]\displaystyle{ \mathrm{Conv}(P) }[/math] of a set [math]\displaystyle{ P\subset \R^d }[/math], then [math]\displaystyle{ x }[/math] can be written as the convex combination of at most [math]\displaystyle{ d+1 }[/math] points in [math]\displaystyle{ P }[/math]. More sharply, [math]\displaystyle{ x }[/math] can be written as the convex combination of at most [math]\displaystyle{ d+1 }[/math] extremal points in [math]\displaystyle{ P }[/math], as non-extremal points can be removed from [math]\displaystyle{ P }[/math] without changing the membership of [math]\displaystyle{ x }[/math] in the convex hull.
Its equivalent theorem for conical combinations states that if a point [math]\displaystyle{ x }[/math] lies in the conical hull [math]\displaystyle{ \mathrm{Cone}(P) }[/math] of a set [math]\displaystyle{ P\subset \R^d }[/math], then [math]\displaystyle{ x }[/math] can be written as the conical combination of at most [math]\displaystyle{ d }[/math] points in [math]\displaystyle{ P }[/math].[1]:257
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.[2]
The result is named for Constantin Carathéodory, who proved the theorem in 1911 for the case when [math]\displaystyle{ P }[/math] is compact.[3] In 1914 Ernst Steinitz expanded Carathéodory's theorem for arbitrary set.[4]
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 = {(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.
Proof
Note: We will only use the fact that [math]\displaystyle{ \R }[/math] is an ordered field, so the theorem and proof works even when [math]\displaystyle{ \R }[/math] is replaced by any field [math]\displaystyle{ \mathbb F }[/math], together with a total order.
We first formally state Carathéodory's theorem:[5]
Carathéodory's theorem — If [math]\displaystyle{ x \in \mathrm{Cone}(S) \subset \R^d }[/math], then [math]\displaystyle{ x }[/math] is the nonnegative sum of at most [math]\displaystyle{ d }[/math] points of [math]\displaystyle{ S }[/math].
If [math]\displaystyle{ x \in \mathrm{Conv}(S) \subset \R^d }[/math], then [math]\displaystyle{ x }[/math] is the convex sum of at most [math]\displaystyle{ d+1 }[/math] points of [math]\displaystyle{ S }[/math].
The essence of Carathéodory's theorem is in the finite case. This reduction to the finite case is possible because [math]\displaystyle{ \mathrm{Conv}(S) }[/math] is the set of finite convex combination of elements of [math]\displaystyle{ S }[/math] (see the convex hull page for details).
Lemma — If [math]\displaystyle{ q_1, ..., q_N \in \R^d }[/math] then [math]\displaystyle{ \forall x \in \mathrm{Conv}(\{q_1, ..., q_N\}) }[/math], exists [math]\displaystyle{ w_1, ..., w_N \geq 0 }[/math] such that [math]\displaystyle{ x = \sum_n w_n q_n }[/math], and at most [math]\displaystyle{ d }[/math] of them are nonzero.
With the lemma, Carathéodory's theorem is a simple extension:
For any [math]\displaystyle{ x\in \mathrm{Conv}(S) }[/math], represent [math]\displaystyle{ x=\sum_{n=1}^N w_n q_n }[/math] for some [math]\displaystyle{ q_1, ..., q_N\in S }[/math], then [math]\displaystyle{ x\in \mathrm{Conv}(\{q_1, ..., q_N\}) }[/math], and we use the lemma.
The second part 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.
Explicitly, let [math]\displaystyle{ S\subset \R^d }[/math], then identify [math]\displaystyle{ \R^d }[/math] with the subset [math]\displaystyle{ \{w \in \R^{d+1}: w_{d+1} = 1\} }[/math]. This induces an embedding of [math]\displaystyle{ S }[/math] into [math]\displaystyle{ S \times \{1\}\subset \R^{d+1} }[/math].
Any [math]\displaystyle{ x\in S }[/math], by first part, has a "lifted" representation [math]\displaystyle{ (x, 1) = \sum_{n=1}^N w_n (q_n, 1) }[/math] where at most [math]\displaystyle{ d+1 }[/math] of [math]\displaystyle{ w_n }[/math] are nonzero. That is, [math]\displaystyle{ x = \sum_{n=1}^N w_n q_n }[/math], and [math]\displaystyle{ 1 =\sum_{n=1}^N w_n }[/math], which completes the proof.
This is trivial when [math]\displaystyle{ N \leq d }[/math]. If we can prove it for all [math]\displaystyle{ N = d+1 }[/math], then by induction we have proved it for all [math]\displaystyle{ N \geq d+1 }[/math]. Thus it remains to prove it for [math]\displaystyle{ N = d+1 }[/math]. This we prove by induction on [math]\displaystyle{ d }[/math].
Base case: [math]\displaystyle{ d=1, N = 2 }[/math], trivial.
Induction case. Represent [math]\displaystyle{ x = \sum_{n=1}^{d+1} w_n q_n }[/math]. If some [math]\displaystyle{ w_n = 0 }[/math], then the proof is finished. So assume all [math]\displaystyle{ w_n \gt 0 }[/math]
If [math]\displaystyle{ \{q_1, ..., q_{d}\} }[/math] is linearly dependent, then we can use induction on its linear span to eliminate one nonzero term in [math]\displaystyle{ \sum_{n=1}^d \frac{w_n}{w_1 + \cdots + w_d}q_n }[/math], and thus eliminate it in [math]\displaystyle{ x = \sum_{n=1}^{d+1} w_n q_n }[/math] as well.
Else, there exists [math]\displaystyle{ (u_1, ..., u_{d}) \in \R^{d} }[/math], such that [math]\displaystyle{ \sum_{n=1}^{d} u_n q_n = q_{d+1} }[/math]. Then we can interpolate a full interval of representations:
[math]\displaystyle{ x = \sum_{n=1}^{d} (w_n+ \theta w_{d+1}u_n) q_n + (1-\theta) w_{d+1} q_{d+1}; \quad \theta\in[0, 1] }[/math]
If [math]\displaystyle{ w_n + w_{d+1} u_n \geq 0 }[/math] for all [math]\displaystyle{ n=1, ..., d }[/math], then set [math]\displaystyle{ \theta = 1 }[/math]. Otherwise, let [math]\displaystyle{ \theta }[/math] be the smallest [math]\displaystyle{ \theta }[/math] such that one of [math]\displaystyle{ w_n + \theta w_{d+1} u_n = 0 }[/math]. Then we obtain a convex representation of [math]\displaystyle{ x }[/math] with [math]\displaystyle{ \leq d }[/math] nonzero terms.
Alternative proofs uses Helly's theorem or the Perron–Frobenius theorem.[6][7]
Variants
Carathéodory's number
For any nonempty [math]\displaystyle{ P\subset \R^d }[/math], define its Carathéodory's number to be the smallest integer [math]\displaystyle{ r }[/math], such that for any [math]\displaystyle{ x\in \mathrm{Conv}(P) }[/math], there exists a representation of [math]\displaystyle{ x }[/math] as a convex sum of up to [math]\displaystyle{ r }[/math] elements in [math]\displaystyle{ P }[/math].
Carathéodory's theorem simply states that any nonempty subset of [math]\displaystyle{ \R^d }[/math] has Carathéodory's number [math]\displaystyle{ \leq d+1 }[/math]. This upper bound is not necessarily reached. For example, the unit sphere in [math]\displaystyle{ \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]\displaystyle{ P\subset \R^d }[/math], upper bounds strictly lower than [math]\displaystyle{ d+1 }[/math] can be obtained.[8]
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.[9]
Colorful Carathéodory theorem
Let X1, ..., Xd+1 be sets in Rd 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 = {x1, ..., xd+1}, where x1 ∈ X1, ..., xd+1 ∈ Xd+1, such that the convex hull of T contains the point x.[10]
By viewing the sets X1, ..., Xd+1 as different colors, the set T is made by points of all colors, hence the "colorful" in the theorem's name.[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.[12]
This theorem has a variant in which the convex hull is replaced by the conical hull.[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. Then there is a set T = {x1, ..., xd}, where x1 ∈ X1, ..., xd ∈ Xd, such that the conical hull of T contains the point x.[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.[13]
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
Notes
- ↑ Lovász, László; Plummer, M. D. (1986), Matching Theory, Annals of Discrete Mathematics, 29, North-Holland, ISBN 0-444-87916-1
- ↑ Danzer, L.; Grünbaum, B.; Klee, V. (1963). "Convexity". 7. American Mathematical Society. pp. 101–179. See in particular p.109
- ↑ Carathéodory, C. (1911). "Über den Variabilitätsbereich der Fourier'schen Konstanten von positiven harmonischen Funktionen" (in de). Rendiconti del Circolo Matematico di Palermo (1884–1940) 32 (1): 193–217[see p.200 bottom]. doi:10.1007/BF03014795. https://link.springer.com/article/10.1007%2FBF03014795.
- ↑ Steinitz, Ernst (1913). "Bedingt konvergente Reihen und konvexe Systeme". J. Reine Angew. Math. 1913 (143): 128–175. doi:10.1515/crll.1913.143.128.
- ↑ Leonard, I. Ed; Lewis, J. E. (2016). "3.3 Convex Hulls". Geometry of convex sets. Hoboken, New Jersey: Wiley Blackwell. ISBN 978-1-119-02266-4.
- ↑ Eggleston, H. G. (1958). Convexity. Cambridge University Press. doi:10.1017/cbo9780511566172. ISBN 9780511566172. http://ebooks.cambridge.org/ref/id/CBO9780511566172. See pages 40–41.
- ↑ Naszódi, Márton; Polyanskii, Alexandr (2021). "Perron and Frobenius Meet Carathéodory". The Electronic Journal of Combinatorics 28 (3). doi:10.37236/9996.
- ↑ Bárány, Imre; Karasev, Roman (2012-07-20). "Notes About the Carathéodory Number" (in en). Discrete & Computational Geometry 48 (3): 783–792. doi:10.1007/s00454-012-9439-z. ISSN 0179-5376.
- ↑ Adiprasito, Karim; Bárány, Imre; Mustafa, Nabil H.; Terpai, Tamás (2019-08-28). "Theorems of Carathéodory, Helly, and Tverberg without dimension". arXiv:1806.08725 [math.MG].
- ↑ 10.0 10.1 10.2 Bárány, Imre (1982-01-01). "A generalization of carathéodory's theorem" (in en). Discrete Mathematics 40 (2–3): 141–152. doi:10.1016/0012-365X(82)90115-7. ISSN 0012-365X.
- ↑ Montejano, Luis; Fabila, Ruy; Bracho, Javier; Bárány, Imre; Arocha, Jorge L. (2009-09-01). "Very Colorful Theorems" (in en). Discrete & Computational Geometry 42 (2): 142–154. doi:10.1007/s00454-009-9180-4. ISSN 1432-0444.
- ↑ 12.0 12.1 Mustafa, Nabil H.; Ray, Saurabh (2016-04-06). "An optimal generalization of the Colorful Carathéodory theorem" (in en). Discrete Mathematics 339 (4): 1300–1305. doi:10.1016/j.disc.2015.11.019. ISSN 0012-365X.
- ↑ Meunier, Frédéric; Mulzer, Wolfgang; Sarrabezolles, Pauline; Stein, Yannik (2017-01-01), "The Rainbow at the End of the Line ? A PPAD Formulation of the Colorful Carathéodory Theorem with Applications", Proceedings of the 2017 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Proceedings (Society for Industrial and Applied Mathematics): pp. 1342–1351, doi:10.1137/1.9781611974782.87, ISBN 978-1-61197-478-2
Further reading
- Eckhoff, J. (1993). "Helly, Radon, and Carathéodory type theorems". Handbook of Convex Geometry. A, B. Amsterdam: North-Holland. pp. 389–448.
- Mustafa, Nabil; Meunier, Frédéric; Goaoc, Xavier; De Loera, Jesús (2019). "The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg" (in en). Bulletin of the American Mathematical Society 56 (3): 415–511. doi:10.1090/bull/1653. ISSN 0273-0979.
External links
- Concise statement of theorem in terms of convex hulls (at PlanetMath)
![]() | Original source: https://en.wikipedia.org/wiki/Carathéodory's theorem (convex hull).
Read more |