Carathéodory's theorem (convex hull)

From HandWiki
Short description: Point in the convex hull of a set P in Rd, is the convex combination of d+1 points in P

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

An illustration of Carathéodory's theorem for a square in R2

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:

Proof of Carathéodory's theorem

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.

Proof of lemma

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

Notes

  1. ↑ Lovász, László; Plummer, M. D. (1986), Matching Theory, Annals of Discrete Mathematics, 29, North-Holland, ISBN 0-444-87916-1 
  2. ↑ Danzer, L.; Grünbaum, B.; Klee, V. (1963). "Convexity". 7. American Mathematical Society. pp. 101–179.  See in particular p.109
  3. ↑ 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. 
  4. ↑ Steinitz, Ernst (1913). "Bedingt konvergente Reihen und konvexe Systeme". J. Reine Angew. Math. 1913 (143): 128–175. doi:10.1515/crll.1913.143.128. 
  5. ↑ 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. 
  6. ↑ 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.
  7. ↑ Naszódi, Márton; Polyanskii, Alexandr (2021). "Perron and Frobenius Meet Carathéodory". The Electronic Journal of Combinatorics 28 (3). doi:10.37236/9996. 
  8. ↑ 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. 
  9. ↑ 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. ↑ 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. 
  11. ↑ 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. ↑ 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. 
  13. ↑ 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



Retrieved from "https://handwiki.org/wiki/index.php?title=Carathéodory%27s_theorem_(convex_hull)&oldid=3371437"