Radon's theorem

From Wikipedia, the free encyclopedia

In geometry, Radon's theorem on convex sets, named after Johann Radon, states that any set of d + 2 points in Rd 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.

Contents

[edit] 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 ai > 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:i\in I\} and X_2=\{x_j:j\in J\}. One point in the intersection of the convex hull of X1 and that of X2 is

\frac{\sum_{i\in I} a_i x_i}{\sum_{i\in I} a_i}.

It is clear that this point is in the convex hull of X1 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 X2. This completes the proof.

[edit] 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.

[edit] See also

[edit] 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 (Full text)
Retrieved from "http://en.wikipedia.org../../../r/a/d/Radon%27s_theorem.html"
In other languages