Centerpoint theorem

Remarks

Consider all closed half-spaces that contain more than $\frac{d}{d+1} n$ points of $X$, and the convex hulls of the points of $X$ in each of them. Each such half-space misses fewer than $\frac{n}{d+1}$ points of $X$, so $d + 1$ of them together miss fewer than $n$ points, and some point of $X$ lies in all $d + 1$ hulls. By Helly's theorem all these hulls have a common point $c$. Suppose a closed half-space containing $c$ had fewer than $\frac{n}{d+1}$ points. Its open complement would contain more than $\frac{d}{d+1} n$ points, and a slightly smaller closed half-space inside it would give a hull that misses $c$, a contradiction. In dimension $1$ a median of $X$ is a centerpoint, with the bound $n/2$. The bound $n/(d+1)$ cannot be improved in general. Take $d + 1$ equal small clusters of points near the vertices of a simplex: for any point $c$, some closed half-space through $c$ meets only one cluster.

Going deeper

For a student

The centerpoint theorem is a standard consequence of Helly's theorem. It generalizes the median to higher dimensions and gives a notion of depth for data. It is used in divide-and-conquer algorithms and in the proof of separator theorems for planar graphs and meshes. The ham sandwich theorem is a different statement about dividing point sets by hyperplanes.