*** Welcome to piglix ***

Radon's theorem


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 disjoint 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.

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.


...
Wikipedia

...