Helly's theorem is a basic result in discrete geometry on the

intersection In mathematics, the intersection of two or more objects is another object consisting of everything that is contained in all of the objects simultaneously. For example, in Euclidean geometry, when two lines in a plane are not parallel, their ...

convex set In geometry, a set of points is convex if it contains every line segment between two points in the set. For example, a solid cube (geometry), cube is a convex set, but anything that is hollow or has an indent, for example, a crescent shape, is n ...

s. It was discovered by Eduard Helly in 1913,. but not published by him until 1923, by which time alternative proofs by and had already appeared. Helly's theorem gave rise to the notion of a Helly family.

Statement

Let be a finite collection of convex subsets of

\R^d

, with

n\geq d+1

. If the intersection of every

d+1

of these sets is nonempty, then the whole collection has a nonempty intersection; that is, :

\bigcap_^n X_j\ne\varnothing.

For infinite collections one has to assume compactness: Let

\

be a collection of

compact Compact as used in politics may refer broadly to a pact or treaty; in more specific cases it may refer to: * Interstate compact, a type of agreement used by U.S. states * Blood compact, an ancient ritual of the Philippines * Compact government, a t ...

convex subsets of

\R^d

, such that every subcollection of

cardinality The thumb is the first digit of the hand, next to the index finger. When a person is standing in the medical anatomical position (where the palm is facing to the front), the thumb is the outermost digit. The Medical Latin English noun for thum ...

at most

d+1

has nonempty intersection. Then the whole collection has nonempty intersection.

Proof

We prove the finite version, using Radon's theorem as in the proof by . The infinite version then follows by the finite intersection property characterization of

compactness In mathematics, specifically general topology, compactness is a property that seeks to generalize the notion of a closed and bounded subset of Euclidean space. The idea is that a compact space has no "punctures" or "missing endpoints", i.e., it ...

: a collection of closed subsets of a compact space has a non-empty intersection if and only if every finite subcollection has a non-empty intersection (once you fix a single set, the intersection of all others with it are closed subsets of a fixed compact space). The proof is by induction: Base case: Let . By our assumptions, for every there is a point that is in the common intersection of all with the possible exception of . Now we apply Radon's theorem to the set which furnishes us with disjoint subsets of such that the

convex hull In geometry, the convex hull, convex envelope or convex closure of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean space, ...

of intersects the convex hull of . Suppose that is a point in the intersection of these two convex hulls. We claim that :

p\in\bigcap_^n X_j.

Indeed, consider any We shall prove that Note that the only element of that may not be in is . If , then , and therefore . Since is convex, it then also contains the convex hull of and therefore also . Likewise, if , then , and by the same reasoning . Since is in every , it must also be in the intersection. Above, we have assumed that the points are all distinct. If this is not the case, say for some , then is in every one of the sets , and again we conclude that the intersection is nonempty. This completes the proof in the case . Inductive Step: Suppose and that the statement is true for . The argument above shows that any subcollection of sets will have nonempty intersection. We may then consider the collection where we replace the two sets and with the single set . In this new collection, every subcollection of sets will have nonempty intersection. The inductive hypothesis therefore applies, and shows that this new collection has nonempty intersection. This implies the same for the original collection, and completes the proof.

Colorful Helly theorem

The colorful Helly theorem is an extension of Helly's theorem in which, instead of one collection, there are ''d''+1 collections of convex subsets of . If, for ''every'' choice of a ''transversal'' – one set from every collection – there is a point in common to all the chosen sets, then for ''at least one'' of the collections, there is a point in common to all sets in the collection. Figuratively, one can consider the ''d''+1 collections to be of ''d''+1 different colors. Then the theorem says that, if every choice of one-set-per-color has a non-empty intersection, then there exists a color such that all sets of that color have a non-empty intersection.

Fractional Helly theorem

For every ''a'' > 0 there is some ''b'' > 0 such that, if are ''n'' convex subsets of , and at least an ''a''-fraction of (''d''+1)-tuples of the sets have a point in common, then a fraction of at least ''b'' of the sets have a point in common.

Notes

References