Proof and Construction
Consider any set of d + 2 points in d-dimensional space. Then there exists a set of multipliers a1, ..., ad + 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 a1, ..., ad + 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.
Read more about this topic: Radon's Theorem
Famous quotes containing the words proof and, proof and/or construction:
“The source of Pyrrhonism comes from failing to distinguish between a demonstration, a proof and a probability. A demonstration supposes that the contradictory idea is impossible; a proof of fact is where all the reasons lead to belief, without there being any pretext for doubt; a probability is where the reasons for belief are stronger than those for doubting.”
—Andrew Michael Ramsay (1686–1743)
“Talk shows are proof that conversation is dead.”
—Mason Cooley (b. 1927)
“There’s no art
To find the mind’s construction in the face.”
—William Shakespeare (1564–1616)