Radon's theorem Information & Radon's theorem Links at HealthHaven.com

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, or if the four points are collinear.

[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 $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:i\in I\}$ and $X_2=\{x_j:j\in J\}$ . One point in the intersection of the convex hull of $X 1$ and that of $X 2$ 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 $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.

[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)

Contents

[edit] Proof

[edit] Tverberg's theorem

[edit] See also

[edit] References