Convexity/Helly's theorem

From Wikibooks, open books for an open world
Jump to navigation Jump to search

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

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.