Carathéodory's theorem (convex hull)

Carathéodory's theorem (convex hull)

:"See also Carathéodory's theorem 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 "P"′ of "P" consisting of "d"+1 or fewer points such that "x" lies in the convex hull of "P"′. Equivalently, "x" lies in a "r"-simplex with vertices in "P", where r leq d. The result is named for Constantin Carathéodory, who proved the theorem in 1911 for the case when "P" is compact. In 1914 Steinitz expanded Carathéodory's theorem for any sets "P" in Rd.

For example, consider a set "P" = {(0,0), (0,1), (1,0), (1,1)} which is a subset of R2. 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)} = "P" ′, the convex hull of which is a triangle and encloses "p", and thus the theorem works for this instance, since |"P"′| = 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, "x" is a convex combination of a finite number of points in "P" :

:mathbf{x}=sum_{j=1}^k lambda_j mathbf{x}_j

where every "x"j is in "P", every "λ"j is positive, and sum_{j=1}^klambda_j=1.

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

:sum_{j=2}^k mu_j (mathbf{x}_j-mathbf{x}_1)=mathbf{0}.

If "μ"1 is defined as

:mu_1:=-sum_{j=2}^k mu_j

then

:sum_{j=1}^k mu_j mathbf{x}_j=mathbf{0}:sum_{j=1}^k mu_j=0

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

:mathbf{x} = sum_{j=1}^k lambda_j mathbf{x}_j-alphasum_{j=1}^k mu_j mathbf{x}_j = sum_{j=1}^k (lambda_j-alphamu_j) mathbf{x}_j

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

: alpha:=min_{1leq j leq k} left{ frac{lambda_j}{mu_j}:mu_j>0 ight}= frac{lambda_i}{mu_i}.

Note that "α">0, and for every "j" between 1 and "k",:lambda_j-alphamu_j geq 0.

In particular, "λ"i − "αμ""i" = 0 by definition of "α". Therefore,

:mathbf{x} = sum_{j=1}^k (lambda_j-alphamu_j) mathbf{x}_j

where every lambda_j - alpha mu_j is nonnegative, their sum is one , and furthermore, lambda_i-alphamu_i=0. In other words, "x" is represented as a convex combination of at most "k"-1 points of "P". This process can be repeated until "x" is represented as a convex combination of at most "d" + 1 points in "P".

Q.E.D.

References

*C. Caratheodory, Über den Variabilitätsbereich der Fourierschen Konstanten von positiven harmonischen Funktionen, Rend. Circ. Mat. Palermo, Vol. 32 (1911), 193-217.

* E. Steinitz, Bedingt konvergente Reihen und konvexe Systeme, I-IV, J. Reine Angew. Math. Vol. 143 (1913), 128-175.

External links

* [http://planetmath.org/encyclopedia/CaratheodorysTheorem2.html Concise statement of theorem] in terms of convex hulls (at PlanetMath)


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • Carathéodory's theorem — In mathematics, Carathéodory s theorem may refer to one of a number of results of Constantin Carathéodory:* Carathéodory s theorem (convex hull) about the convex hulls of sets in Euclidean space *Carathéodory s theorem (measure theory) about… …   Wikipedia

  • Convex hull — The convex hull of the red set is the blue convex set. See also: Convex set and Convex combination In mathematics, the convex hull or convex envelope for a set of points X in a real vector space V is the min …   Wikipedia

  • Hull — may refer to: *Kingston upon Hull (invariably abbreviated to Hull), city in England named after the River Hull (Kings town upon Hull, prior to 1299 Wyke upon Hull) ** River Hull, river in East Riding of Yorkshire, England ** Hull City A.F.C.,… …   Wikipedia

  • Convex set — A convex set …   Wikipedia

  • Convex combination — Given three points x1,x2,x3 in a plane as shown in the figure, the point P is a convex combination of the three points, while Q is not. (Q is however an affine combination of the three poin …   Wikipedia

  • Constantin Carathéodory — Born 13 September 1873 …   Wikipedia

  • Radon's theorem — In geometry, Radon s theorem on convex sets, named after Johann Radon, states that any set of d+2 points in R d can be partitioned into two (disjoint) sets whose convex hulls intersect. A point in the intersection of these hulls is called a Radon …   Wikipedia

  • List of mathematics articles (C) — NOTOC C C closed subgroup C minimal theory C normal subgroup C number C semiring C space C symmetry C* algebra C0 semigroup CA group Cabal (set theory) Cabibbo Kobayashi Maskawa matrix Cabinet projection Cable knot Cabri Geometry Cabtaxi number… …   Wikipedia

  • List of theorems — This is a list of theorems, by Wikipedia page. See also *list of fundamental theorems *list of lemmas *list of conjectures *list of inequalities *list of mathematical proofs *list of misnamed theorems *Existence theorem *Classification of finite… …   Wikipedia

  • List of convexity topics — This is a list of convexity topics, by Wikipedia page. Alpha blending Barycentric coordinates Borsuk s conjecture Bond convexity Carathéodory s theorem (convex hull) Choquet theory Closed convex function Concavity Convex analysis Convex… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”