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/or construction:
“When children feel good about themselves, it’s like a snowball rolling downhill. They are continually able to recognize and integrate new proof of their value as they grow and mature.”
—Stephanie Martson (20th century)
“No real “vital” character in fiction is altogether a conscious construction of the author. On the contrary, it may be a sort of parasitic growth upon the author’s personality, developing by internal necessity as much as by external addition.”
—T.S. (Thomas Stearns)