18 I. Convex Sets at Large
Hence v is a convex combination of points from R and a convex combination of
points from B. In other words, v ∈ conv(R) and v ∈ conv(B).
Figure 5. Example: for any set of four points in the plane, either one
of the points lies within the convex hull of the other three, or the points
can be split into two pairs whose convex hulls intersect.
Show by an example that the constant d + 2 in Radon’s Theorem cannot
be improved to d + 1.
(Tverberg’s Theorem). Let k ≥ 2. Prove that for any set S of (k−1)(d+1)+1
or more points in
one can find k pairwise non-intersecting subsets A1,... , Ak ⊂
S such that the intersection
conv(A1) ∩ conv(A2) ∩ . . . ∩ conv(Ak)
is not empty. Show that for some sets of (k − 1)(d + 1) points, such subsets
A1,... , Ak cannot be found.
Remark: See, for example, Chapter 8 of [Mat02].
The following result (one of the most famous results in convexity) was discov-
ered by E. Helly in 1913. The proof below is due to Radon (1921).
(4.2) Helly’s Theorem. Let A1,... , Am, m ≥ d + 1, be a finite family of convex
Suppose that every d + 1 of the sets have a common point:
Ai1 ∩ . . . ∩ Aid+1 = ∅.
Then all the sets have a common point:
A1 ∩ . . . ∩ Am = ∅.