Radon's theorem

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 point of the set.

For example, in the case d=2, the set, call it X, would consist of four points. Depending on the set, it might be possible to partition X, into a triple and a singleton, where the convex hull of the triple (a triangle) contains the singleton, or it would be possible to partition X, into two pairs of points such that the line segments with these points as endpoints intersect. The latter situation would be the case if X, consists of the vertices of a convex quadrilateral.

Proof

The proof of Radon's theorem is not too difficult. Suppose X = {x_1,x_2,dots,x_{d+2}}subset mathbf{R}^d. Since any set of d+2 points in mathbf{R}^d is affinely dependent, there exists a set of multipliers a_1,ldots,a_{d+2} not all zero such that the system of equations

: sum_{i=1}^{d+2} a_i x_i=0

: sum_{i=1}^{d+2} a_i=0

is satisfied. Fix some nonzero solution a_1,a_2,dots,a_{d+2}. Let I be the subset of {1,2,dots,d+2} such that a_i > 0 for all i in I, and let J be the subset of {1,2,dots,d+2} such that a_j leq 0 for all j in J. The required partition of X is X_1={x_i:iin I} and X_2={x_j:jin J}. One point in the intersection of the convex hull of X_1 and that of X_2 is

: frac{sum_{iin I} a_i x_i}{sum_{iin I} a_i}.

It is clear that this point is in the convex hull of X_1 and it is an easy consequence of the above equations satisfied by a_1,dots,a_{d+2} that this point is also in the convex hull of X_2. This completes the proof.

Tverberg's theorem

A generalisation for partition into "r" sets was given in 1966 by Helge Tverberg. It states that for

:("d" + 1)("r" − 1) + 1

points in Euclidean "d"-space, there is a partition into "r" subsets (Tverberg partition) having convex hulls intersecting in at least one common point.

ee also

* Helly's theorem
* Carathéodory's theorem.

References

*J. Eckhoff, Helly, Radon, and Carathéodory type theorems, Handbook of convex geometry, Vol. A, B, 389-448, North-Holland, Amsterdam, 1993.

*J. Radon, Mengen konvexer Körper, die einen gemeinsamen Punkt enthalten, Math. Ann. Vol. 83 (1921), 113--115.

*H. Tverberg, A generalization of Radon's theorem, J. Lond. Math. Soc. Vol. 41 (1966), 123-128.

*S. Hell, Tverberg-type theorems and the Fractional Helly property, Dissertation, TU Berlin 2006 ( [http://opus.kobv.de/tuberlin/volltexte/2006/1416/ Full text] )


Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Look at other dictionaries:

  • Radon–Nikodym theorem — In mathematics, the Radon–Nikodym theorem is a result in functional analysis that states that, given a measurable space ( X , Sigma;), if a sigma finite measure nu; on ( X , Sigma;) is absolutely continuous with respect to a sigma finite measure… …   Wikipedia

  • Radon transform — In mathematics, the Radon transform in two dimensions, named after the Austrian mathmematician Johann Radon, is the integral transform consisting of the integral of a function over straight lines. The inverse of the Radon transform is used to… …   Wikipedia

  • Radon measure — In mathematics (specifically, measure theory), a Radon measure, named after Johann Radon, is a measure on the σ algebra of Borel sets of a Hausdorff topological space X that is locally finite and inner regular. Contents 1 Motivation 2 Definitions …   Wikipedia

  • Stinespring factorization theorem — In mathematics, Stinespring s dilation theorem, also called Stinespring s factorization theorem, is a result from operator theory that represents any completely positive map on a C* algebra as a composition of two completely positive maps each of …   Wikipedia

  • Johann Radon — Infobox Scientist name = Johann Radon box width = 26em image width = 225px caption = birth date = 1887 12 16 birth place = Děčín, Bohemia, Austria Hungary death date = death date and age|1956|5|25|1887|12|16 death place = Vienna, Austria… …   Wikipedia

  • Helly's theorem — In geometry, Helly s theorem is a basic combinatorial result on convex sets. It was proved by Eduard Helly in 1923, and gave rise to the notion of Helly family.tatement of Helly s theorem:Suppose that::X 1,X 2,dots,X n :is a finite collection of… …   Wikipedia

  • Choi's theorem on completely positive maps — In mathematics, Choi s theorem on completely positive maps (after Man Duen Choi) is a result that classifies completely positive maps between finite dimensional (matrix) C* algebras. An infinite dimensional algebraic generalization of Choi s… …   Wikipedia

  • Théorème de Radon (géométrie) — Sommaire 1 Énoncé 2 Preuve 3 Théorème de Tverberg 4 Notes et références Énoncé Le théorème de …   Wikipédia en Français

  • Plancherel theorem for spherical functions — In mathematics, the Plancherel theorem for spherical functions is an important result in the representation theory of semisimple Lie groups, due in its final form to Harish Chandra. It is a natural generalisation in non commutative harmonic… …   Wikipedia

  • Lebesgue's decomposition theorem — In mathematics, more precisely in measure theory, Lebesgue s decomposition theorem is a theorem which states that given mu and u two sigma; finite signed measures on a measurable space (Omega,Sigma), there exist two sigma; finite signed measures… …   Wikipedia

Share the article and excerpts

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