Science Fair Project Encyclopedia

Science Fair Project Encyclopedia Contents Page

Categories: Convex geometry | Discrete geometry | Theorems

Radon's theorem

In geometry, Radon's theorem on convex sets states that any set of $d + 2$ points in R^d can be partitioned into two (disjoint) sets whose convex hulls intersect.

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 rectangle.

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$ . The system of equations

$\sum_{j=1}^{d+2} a_j x_j=0$

$\sum_{j=1}^{d+2} a_j=0$

can be thought of as a system of $d + 1$ equations in $d + 2$ unknowns $a_1,a_2,\dots,a_{d+2}$ , since the first equation is really a vector equation in dimension $d$ . There must therefore be a nonzero solution. Fix some nonzero solution $a_1,a_2,\dots,a_{d+2}$ . Let $I$ be the set of $i=1,2,\dots,d+2$ such that $a i > 0$ , and let $J$ be the set of $i=1,2,\dots,d+2$ such that $a i < 0$ . The required partition of $X$ is $X_1=\{x_i:i\in I\}$ and $X_2=\{x_i:i\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.

References:

H. G. Eggleston, Convexity, Cambridge Univ. Press.
S. R. Lay, Convex Sets and Their Applications, Wiley.

Categories: Convex geometry | Discrete geometry | Theorems

Last updated: 05-27-2005 06:51:38

Science Fair Project Encyclopedia Contents Page

10-26-2009 08:16:03
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details

All Science Fair Projects