PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (192)
Orphanage
Unclass'd (1)
Unproven (490)
Corrections (6)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: High Entry average rating: No information on entry rating
Radon's lemma (Theorem)

Every set $ A\subset \mathbb{R}^d$ of $ d+2$ or more points can be partitioned into two disjoint sets $ A_1$ and $ A_2$ such that the convex hulls of $ A_1$ and $ A_2$ intersect.

Proof. Without loss of generality we assume that the set $ A$ consists of exactly $ d+2$ points which we number $ a_1, a_2,\dotsc, a_{d+2}$. Denote by $ a_{i,j}$ the $ j$'th component of $ i$'th vector, and write the components in a matrix as
$\displaystyle M=\begin{bmatrix}a_{1,1}&a_{2,1}&\dots&a_{d+2,1}\\ a_{1,2}&a_{2,2... ...&\ddots & \vdots\\ a_{1,d}&a_{2,d}&\dots&a_{d+2,d}\\ 1&1&\dots&1 \end{bmatrix}.$    

Since $ M$ has fewer rows than columns, there is a non-zero column vector $ \mathbf{\lambda}$ such that $ M \mathbf{\lambda}=0$, which is equivalent to the existence of a solution to the system
0 $\displaystyle =\lambda_1 a_1+\lambda_2 a_2+\dotsb+\lambda_{d+2} a_{d+2}$ (1)
0 $\displaystyle =\lambda_1+\lambda_2+\dotsb+\lambda_{d+2}$    

Let $ A_1$ be the set of those $ a_i$ for which $ \lambda_i$ is positive, and $ A_2$ be the rest. Set $ s$ to be the sum of positive $ \lambda_i$'s. Then by the system (1) above
$\displaystyle \frac{1}{s}\sum_{a_i\in A_1} \lambda_i a_i=\frac{1}{s}\sum_{a_i\in A_2} (-\lambda_i) a_i$    

is a point of intersection of convex hulls of $ A_1$ and $ A_2$. $ \qedsymbol$



"Radon's lemma" is owned by bbukh.
(view preamble)

View style:

Keywords:  convex hull
Log in to rate this entry.
(view current ratings)

Cross-references: sum, positive, solution, equivalent, column vector, columns, rows, matrix, vector, component, number, without loss of generality, intersect, convex hulls, disjoint, points
There are 2 references to this entry.

This is version 5 of Radon's lemma, born on 2003-09-07, modified 2006-02-05.
Object id is 4710, canonical name is RadonsLemma.
Accessed 2536 times total.

Classification:
AMS MSC: 52C07 (Convex and discrete geometry :: Discrete geometry :: Lattices and convex bodies in $n$ dimensions)
 52A20 (Convex and discrete geometry :: General convexity :: Convex sets in $n$ dimensions )
Pending Errata and Addenda
None.
[ View all 2 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | prove | add result | add corollary | add example | add (any)