Editing Radon's theorem (section)

==Proof and construction==
Consider any set <math>X=\{x_1,x_2,\dots,x_{d+2}\}\subset \mathbf{R}^d</math> of ''d''&nbsp;+&nbsp;2 points in ''d''-dimensional space. Then there exists a set of multipliers ''a''<sub>1</sub>,&nbsp;...,&nbsp;''a''<sub>''d''&nbsp;+&nbsp;2</sub>, not all of which are zero, solving the [[system of linear equations]]
:<math> \sum_{i=1}^{d+2} a_i x_i=0,\quad \sum_{i=1}^{d+2} a_i=0,</math>
because there are ''d''&nbsp;+&nbsp;2 unknowns (the multipliers) but only ''d''&nbsp;+&nbsp;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''<sub>1</sub>,&nbsp;...,&nbsp;''a''<sub>''d''&nbsp;+&nbsp;2</sub>. Let <math>I\subseteq X</math> be the set of points with positive multipliers, and let <math>J=X\setminus I</math> be the set of points with multipliers that are negative or zero. Then <math>I</math> and <math>J</math> form the required partition of the points into two subsets with intersecting convex hulls.

The convex hulls of <math>I</math> and <math>J</math> must intersect, because they both contain the point
:<math>p= \sum_{x_i\in I}\frac{a_i}{A} x_i=\sum_{x_j\in J}\frac{-a_j}{A}x_j,</math>
where
:<math>A=\sum_{x_i\in I} a_i=-\sum_{x_j\in J} a_j.</math>
The left hand side of the formula for <math>p</math> expresses this point as a [[convex combination]] of the points in <math>I</math>, and the right hand side expresses it as a convex combination of the points in <math>J</math>. Therefore, <math>p</math> 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 time|polynomial]] in the dimension, by using [[Gaussian elimination]] or other efficient algorithms to solve the system of equations for the multipliers.<ref name="cemst">{{harvtxt|Clarkson|Eppstein|Miller|Sturtivant|1996}}.</ref>