Helly's Theorem
Helly's theorem is a statement about intersections of convex sets. A general theorem is as follows:
It is a well publicized fact that Eduard Helly published a proof of the theorem that bears his name in 1923, two years after Johann Radon published his. Alexander Soifer in his recent book gave an explanation to an apparent injustice:
(the theorem) ... was discovered by the Austrian mathematician Eduard Helly (Vienna, 1884 - Chicago, 1943), in 1913. But it was not published at that time. During World War I, Helly was a soldier in the Austrian Army, and he was taken a Russian prisoner in 1914. He explained his theorem to another Austrian mathematician who was in Russian captivity as well.
The theorem lived in mathematical folklore from the time of these mysterious meeting of two mathematical prisoners until 1921 when the first proof of the Helly theorem was published by the Austrian mathematician Johann Karl August Radon (with a reference to Helly). In 1923 Helly published his own proof (different from Radon's!).
I shall give a simple proof of the theorem in R² as it appears in the classical book of V. Boltyanski and I. Yaglom. The proof has been reproduced in [Etudes] by A. Soifer.
The proof starts with a particular case
Lemma
Proof of Lemma
Denote the four sets F1, F2, F3, F4. For j = 1, 2, 3, 4, let aj be a common point of the three sets, with Fj removed. Thus, for example,
One of the points a1, a2, a3, a4 lies in the interior or the border of the triangle formed by the other three. Assume, for example, that
a1 ∈ Δa2a3a4. But each of the points a2, a3, a4 belongs to F1. By the convexity of the latter, the wholeΔa2a3a4 ⊂ F1 and soa1 ∈ F1. Since, by our assumption,a1 ∈ F2 ∩ F3 ∩ F4, we also havea1 ∈ F1 ∩ F2 ∩ F3 ∩ F4. Points a1, a2, a3, a4 form a convex quadrilateral, so that none of them lies in the triangle formed by the other three. The diagonal a1a3 wholly belongs to
F2 ∩ F4 while the diagonal a2a4 wholly belongs toF1 ∩ F3. The intersection of the diagonals then belongs to(F2 ∩ F4) ∩ (F1 ∩ F3).
Proof of Helly's Theorem (in R²)
The proof is by induction on the number s of sets in C. The case of s = 4 is covered by Lemma. So let's assume that the theorem holds for some
Define Gk = Fk ∩ Fs+1, k = 1, ..., s. The intersection of any three G's is nonempty. For example,
which is nonempty by Lemma. This means that the intersection of all G's is nonempty. But the intersection of all G's is exactly the intersection of all F's.
References
- B. Bollobás, The Art of Mathematics, Cambridge University Press, 2006, p. 90-91
- A. Soifer, Geometric Etudes in Combinatorial Mathematics, Springer, 2010 (2nd, expanded edition)
- Yaglom, I. M.and V. G. Boltyanski, Convex Figures, Holt, Rinehart and Winstion, 1961
Convex Sets
- Helly's Theorem
- First Applications of Helly's Theorem
- Crossed-Lines Construction of Shapes of Constant Width
- Shapes of constant width (An Interactive Gizmo)
- Star Construction of Shapes of Constant Width
- Convex Polygon Is the Intersection of Half Planes
- Minkowski's addition of convex shapes
- Perimeters of Convex Polygons, One within the Other
- The Theorem of Barbier
- A. Soifer's Book, P. Erdos' Conjecture, B. Grunbaum's Counterexample
- Reuleaux's Triangle, Extended
|Contact| |Front page| |Contents| |Geometry|
Copyright © 1996-2018 Alexander Bogomolny
71471701