What collections of convex sets result in non-trivial uses of Helly's theorem?

Question

Consider Helly Theorem, taken from notes by Igor Pak:

Let $X_1, \dots, X_n \in {\mathbb{R}}^2$ be convex regions in the plane such that any triple interesects $X_i \cap X_j \cap X_k \neq 0$. Then there is a point in all the sets, $X_1 \cap \dots \cap X_n \neq \varnothing$.

This result is not obvious (although Pak's proof is short). However, any explicit collection of sets I build such that three of them intersect, have a clear total intersection. How about this simpler result, also from Pak's book:

Let $P_1, \dots, P_n \in {\mathbb R}^2$ be rectangles with sides parallel to the coordinate axes, such that any two intersect each other. Then all the rectangles have a nonempty intersection.

By Helly's theorem, we only need $n = 3$. What happens if we don't use Helly's theorem and try to prove this result directly?

Let $[x_1, x_1']\times [y_1, y_1'], \dots, [x_n, x_n']\times [y_n, y_n'] \in {\mathbb R}^2$ be rectangles in the plane, sides parallel to the $x,y$-axes, such that:

$x_i < x_j < x_i' < x_j'$ (or vice-versa) and $y_i < y_j < y_i' < y_j'$ (or vice-versa).

Then $x_i < x_j'$ for all $i,j$ and $y_i < y_j'$ for all $i,j$. So $[\mathrm{max} (x_i) , \mathrm{min} (x_i')] \times [\mathrm{max} (y_i) , \mathrm{min}( y_i')]$ is a rectangle that works.

Here, it wasn't hard to find that intersection point even without the reduction from Helly's theorem.

---

What kind of interesting collections of convex sets result in non-trivial uses of Helly's theorem?

http://s15.postimage.org/8pjy7dfcp/rectangles.gif

Answer 1

Suppose you have a bounded convex region $R$ of volume $1$ in $\mathbb{R}^d$. Consider convex subsets of volume greater than $\frac {d}{d+1}.$ By the union bound, there is some point in the intersection of any $d+1$, so by Helly's theorem there is a point contained in any convex subset of volume greater than $\frac{d}{d+1}$.

It's not obvious to me what the best replacement for $\frac{d}{d+1}$ is in that last statement, but there are convex subsets of a triangle of volume up to $5/9$ which do not contain the centroid, or at least $1-(\frac d{d+1})^d \sim 1-\frac1e$ in dimension $d$.

Barvinok, A Course in Convexity p. 23 says a measure-theoretic version of the above result was proved by Radon in 1916. That was shortly after Helly's theorem was proved.

Answer 2

You are saying that if a collection of planar sets does have a non-empty intersection it is visually obvious so what use is a theorem asserting the fact (at least if they are convex and we can see them all at the same time?)

The interesting thing is not the examples, it is the lack of counter-examples. It is easy to draw $n$ convex sets in the plane so that no two are disjoint yet no point is common to all of them. Can you change two to three? It does not seem like it but that is no proof. You can change to three for bodies in $\mathbb{R}^3$ but not four. The problem is understandable for $\mathbb{R}^m$ but geometric intuition may be weaker.

Here is a proof of Let $M$ be a finite set of points in the plane, with all pairwise distance between them not exceeding $1$. Then $M$ is contained in a disk of radius $\frac{1}{\sqrt3}$. See if you can figure out the short proof. So again in any specific case perhaps we can find an appropriate circle but we need the theorem to say that we won't find a counter-example.

This seems more contrived, but I can attack "at the same time." imagine that I give you $\binom53=10$ cards each with a picture of three colored ovals ( all possible combinations of red, blue , green , yellow and black. ) I tell you that these are the same five sets, viewed three at a time. My claim looks reasonable and you can see that every triple has a non-empty intersection. It might not be obvious where a common point of all five is, but if I am telling the truth then there must be one.