---
tag: 888R24ZGNY
kind: statement
role: theorem
name: Radon's theorem
msc: [52A35]
uses: [0XPR1E85W0, 0FQSDC2EQ2, 08QMKTWF9T]
about: [0FQSDC2EQ2]
sources:
  - url: https://en.wikipedia.org/wiki/Radon%27s_theorem
same_as:
  wikidata: Q1471282
  wikipedia: Radon's theorem
---

## Statement

Let $d \ge 1$ and let $X \subseteq \R^d$ be a finite set with at least $d + 2$ points.
Then $X$ can be [[partitioned|08QMKTWF9T]] into two disjoint sets $A$ and $B$ whose [[convex hulls|0FQSDC2EQ2]] intersect:
$$\operatorname{conv}(A) \cap \operatorname{conv}(B) \ne \emptyset.$$

## Remarks

Proof idea: take $d + 2$ points $x_1, \dots, x_{d+2}$ of $X$.
The $d + 2$ vectors $(x_i, 1) \in \R^{d+1}$ are linearly dependent, so there are reals $\lambda_i$, not all $0$, with $\sum \lambda_i x_i = 0$ and $\sum \lambda_i = 0$.
Let $A$ hold the points with $\lambda_i > 0$ and let $B$ hold the rest, and put $s = \sum_{\lambda_i > 0} \lambda_i > 0$.
Then $\sum_{\lambda_i > 0} (\lambda_i / s) x_i = \sum_{\lambda_i \le 0} (-\lambda_i / s) x_i$ is a point of both hulls; the remaining points of $X$ can be added to either part.

Example: take four points in the plane.
If one of them lies in the convex hull of the other three, that point against the other three is a Radon partition.
Otherwise they are the vertices of a convex quadrilateral, and its two diagonals cross.

The number $d + 2$ is sharp: the $d + 1$ vertices of a simplex in $\R^d$ are affinely independent, and no partition of them has intersecting hulls.

## Explanations

### L1 human

Take any $d + 2$ points in $d$-dimensional space, for example four points in the plane.
You can always colour them red and blue so that the red shape and the blue shape overlap.
With three points in the plane this can fail: the corners of a triangle cannot be split this way.

### L2 human

Radon's theorem is the key step in a short proof of Helly's theorem.
It also shows that half-spaces in $\R^d$ have VC dimension at most $d + 1$ in learning theory, since no set of $d + 2$ points can be shattered.
Its generalisation to partitions into more than two parts is Tverberg's theorem, and a topological version replaces convex hulls by images of faces of a simplex under continuous maps.