Radon's Theorem - Proof and Construction

Proof and Construction

Consider any set of d + 2 points in d-dimensional space. Then there exists a set of multipliers a₁, ..., a_{d + 2}, not all of which are zero, solving the system of linear equations

because there are d + 2 unknowns (the multipliers) but only d + 1 equations that they must satisfy (one for each coordinate of the points, together with a final equation requiring the sum of the multipliers to be zero). Fix some particular nonzero solution a₁, ..., a_{d + 2}. Let I be the set of points with positive multipliers, and let J be the set of points with multipliers that are negative or zero. Then I and J form the required partition of the points into two subsets with intersecting convex hulls.

The convex hulls of I and J must intersect, because they both contain the point

where

The left hand side of the formula for p expresses this point as a convex combination of the points in I, and the right hand side expresses it as a convex combination of the points in J. Therefore, p belongs to both convex hulls, completing the proof.

This proof method allows for the efficient construction of a Radon point, in an amount of time that is polynomial in the dimension, by using Gaussian elimination or other efficient algorithms to solve the system of equations for the multipliers.