In geometry, Radon's theorem on convex sets, published by Johann Radon in 1921, states that:Any set of d + 2 points in Rd can be partitioned into two sets whose convex hulls intersect. A point in the intersection of these convex hulls is called a Radon point of the set.For example, in the case d = 2, any set of four points in the Euclidean plane can be partitioned in one of two ways. It may form a triple and a singleton, where the convex hull of the triple (a triangle) contains the singleton; alternatively, it may form two pairs of points that form the endpoints of two intersecting line segments.
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 be the set of points with positive multipliers, and let be the set of points with multipliers that are negative or zero. Then and form the required partition of the points into two subsets with intersecting convex hulls.
The convex hulls of and must intersect, because they both contain the point
where
The left hand side of the formula for expresses this point as a convex combination of the points in , and the right hand side expresses it as a convex combination of the points in . Therefore, 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.
Topological Radon theorem
An equivalent formulation of Radon's theorem is:If ƒ is any affine function from a (d + 1)-dimensional simplex Δd+1 to Rd, then there are two disjoint faces of Δd+1 whose images under ƒ intersect.They are equivalent because any affine function on a simplex is uniquely determined by the images of its vertices. Formally, let ƒ be an affine function from Δd+1 to Rd. Let be the vertices of Δd+1, and let be their images under ƒ. By the original formulation, the can be partitioned into two disjoint subsets, e.g. (xi)i in I and (xj)j in J, with overlapping convex hull. Because f is affine, the convex hull of (xi)i in I is the image of the face spanned by the vertices (vi)i in I, and similarly the convex hull of (xj)j in J is the image of the face spanned by the vertices (vj)j in j. These two faces are disjoint, and their images under f intersect - as claimed by the new formulation.
The topological Radon theorem generalizes this formluation. It allows f to be any continuous function - not necessarily affine:If ƒ is any continuous function from a (d + 1)-dimensional simplex Δd+1 to Rd, then there are two disjoint faces of Δd+1 whose images under ƒ intersect.More generally, if K is any (d + 1)-dimensional compact convex set, and ƒ is any continuous function from K to d-dimensional space, then there exists a linear function g such that some point where g achieves its maximum value and some other point where g achieves its minimum value are mapped by ƒ to the same point. In the case where K is a simplex, the two simplex faces formed by the maximum and minimum points of g must then be two disjoint faces whose images have a nonempty intersection. This same general statement, when applied to a hypersphere instead of a simplex, gives the Borsuk–Ulam theorem, that ƒ must map two opposite points of the sphere to the same point.
Proofs
The topological Radon theorem was originally proved by Bajmoczy and Barany in the following way:
Construct a continuous map g from Sd (the d-dimensional sphere) to Δd+1, such that for every point x on the sphere, g(x) and g(-x) are on two disjoint faces of Δd+1. Apply the Borsuk–Ulam theorem to the function , which is a continuous function from Sd to Rd. The theorem says that, for any such function, there exists some point y on Sd, such that f(g(y)) = f(g(-y)). The points g(y) and g(-y) are on two disjoint faces of Δd+1, and they are mapped by f to the same point of Rd. This implies that the images of these two disjoint faces intersect.
Another proof was given by Lovasz and Schrijver. A third proof is given by Matousek: