|
|
|
|
|
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
 . Denote by $a_{i,j}$ the $j$ 'th component of $i$ 'th vector, and write the components in a matrix as \begin{equation*} M=\begin{bmatrix} a_{1,1}&a_{2,1}&\dots&a_{d+2,1}\\ a_{1,2}&a_{2,2}&\dots&a_{d+2,2}\\ \vdots& \vdots&\ddots & \vdots\\ a_{1,d}&a_{2,d}&\dots&a_{d+2,d}\\ 1&1&\dots&1 \end{bmatrix}. \end{equation*}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
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 \begin{equation*} \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 \end{equation*}is a point of intersection of convex hulls of $A_1$ and $A_2$ . 
|
"Radon's lemma" is owned by bbukh.
|
|
(view preamble | get metadata)
Cross-references: intersection, sum, positive, solution, equivalent, column vector, columns, rows, matrix, components, 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 3233 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
|
|
|
|
|
|
|
|
|
|
|