Convexity/Helly's theorem

Helly's theorem is as follows:

Let Rn be an n-dimensional real vector space and let N > n. Suppose you have N convex sets in Rn such that, given any n+1 of them, they have at least one point in common. Then all N sets have at least one point in common.

Proof: Obviously, the theorem is true for N = n+1. Proceed by induction and assume it is true for N-1. Let the sets be X1 to XN. For each i, exclude set Xi. By the inductive hypothesis, there is at least one point x(i) belonging to all the sets except possibly Xi. Since N > n+1, the (n+1) equations

\displaystyle \sum_{i=1}^N \lambda_i x_k(i) = 0
\displaystyle(k=1,2, ... n)
\displaystyle \sum_{i=1}^N \lambda_i = 0

in the N unknowns λ1 to λN must have non-trivial solutions. For one such solution, denote by λj1 to λjk those λ that are positive, and λh1 to λh(N-k) those that are negative.


Last modified on 10 April 2011, at 17:34