Radon’s lemma

Every set Ad of d+2 or more points can be partitioned into two disjoint sets A1 and A2 such that the convex hullsMathworldPlanetmath of A1 and A2 intersect.


Without loss of generality we assume that the set A consists of exactly d+2 points which we number a1,a2,,ad+2. Denote by ai,j the j’th componentPlanetmathPlanetmathPlanetmath of i’th vector, and write the components in a matrix as


Since M has fewer rows than columns, there is a non-zero column vectorMathworldPlanetmath λ such that Mλ=0, which is equivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmath to the existence of a solution to the system

0 =λ1a1+λ2a2++λd+2ad+2 (1)
0 =λ1+λ2++λd+2

Let A1 be the set of those ai for which λi is positive, and A2 be the rest. Set s to be the sum of positive λi’s. Then by the system (1) above


is a point of intersection of convex hulls of A1 and A2. ∎

Title Radon’s lemma
Canonical name RadonsLemma
Date of creation 2013-03-22 13:56:48
Last modified on 2013-03-22 13:56:48
Owner bbukh (348)
Last modified by bbukh (348)
Numerical id 8
Author bbukh (348)
Entry type Theorem
Classification msc 52A20
Classification msc 52C07