Abstract

Helly's theorem is an important result from Convexity and Combinatorial Geometry. It gives sufficient conditions for a family of convex sets to have a nonempty intersection. A large variety of proofs as well as applications are known. Helly's theorem has close connections to two other well-known theorems: Radon's theorem and Carathéodory's theorem. In this paper we study Helly's theorem and its relations to Radon's theorem and Carathéodory's theorem by using tools of Convex Analysis and Optimization. More precisely, we will give a new proof of Helly's theorem, and in addition we show in a complete way that these three theorems are equivalent in the sense that using one of them allows us to derive the others.

Author information

Contact details are reproduced from the original publication and may be historical.

Nguyen Mau Nam

Fariborz Maseeh Dept. of Mathematics and Statistics, Portland State University, PO Box 751, Portland, OR 97207, U.S.A.

mau.nam.nguyen@pdx.edu

Adam Robinson

Fariborz Maseeh Dept. of Mathematics and Statistics, Portland State University, PO Box 751, Portland, OR 97207, U.S.A.

ad7@pdx.edu

Keywords

  • Carathéodory's theorem
  • convex function
  • convex hull
  • distance function
  • Helly's theorem
  • Radon's theorem
  • subdifferential
  • subgradient

Mathematics Subject Classification

52A05, 52A20, 52A35, 52A37

References

  1. V. Boltyanski, H. Martini: Carathéodory’s theorem and H-convexity, J. Comb. Theory, Ser. A 93 (2001) 292–309.https://doi.org/10.1006/jcta.2000.3080Google Scholar
  2. V. Boltyanski, H. Martini: Minkowski addition of H-convex sets and related Helly-type theorems, J. Comb. Theory, Ser. A 103 (2003) 323–336.https://doi.org/10.1016/S0097-3165(03)00101-8Google Scholar
  3. V. Boltyanski, H. Martini, P. S. Soltan: Excursions into Combinatorial Geometry, Springer, Berlin (1997).https://doi.org/10.1007/978-3-642-59237-9Google Scholar
  4. S. Boyd, L. Vandenberghe: Convex Optimization, Cambridge University Press, Cambridge (2004).https://doi.org/10.1017/CBO9780511804441Google Scholar
  5. L. Danzer, B. Grünbaum, V. Klee: Helly’s theorem and its relatives, in: Convexity (Seattle, 1961), V. Klee (ed.), Proc. Symp. Pure Math. 7, American Mathematical Society, Providence (1963) 101–180.https://doi.org/10.1090/pspum/007/0157289Google Scholar
  6. J. Eckhoff: Helly, Radon and Carathéodory type theorems, in: Handbook of Convexity. Vol. A, P. M. Gruber, J. M. Wills (eds.), North-Holland, Amsterdam (1993) 389–448.https://doi.org/10.1016/B978-0-444-89596-7.50017-1Google Scholar
  7. H. G. Eggleston: Convexity, Cambridge Tracts in Mathematics and Mathematical Physics 47, Cambridge University Press, Cambridge (1958).Google Scholar
  8. P. M. Gruber: History of convexity, in: Handbook of Convexity. Vol. A, P. M. Gruber, J. M. Wills (eds.), North-Holland, Amsterdam (1993) 1–15.https://doi.org/10.1016/B978-0-444-89596-7.50005-5Google Scholar
  9. P. M. Gruber: Convex and Discrete Geometry, Springer, Berlin (2007).Google Scholar
  10. B. Mordukhovich, N. M. Nam: An Easy Path to Convex Analysis and Applications, Morgan and Claypool, San Rafael (2014).https://doi.org/10.1007/978-3-031-02406-1Google Scholar
  11. J.-J. Moreau: Fonctions convexes duales et points proximaux dans un espace hilbertien, C. R. Acad. Sci., Paris 255 (1962) 2897–2899.Google Scholar
  12. J.-J. Moreau: Fonctionnelles sous-différentiables, C. R. Acad. Sci., Paris 257 (1963) 4117–4119.Google Scholar
  13. J.-J. Moreau: Proximité dualité dans espace hilbertien, Bull. Soc. Math. Fr. 93 (1965) 273–299.https://doi.org/10.24033/bsmf.1625Google Scholar
  14. R. T. Rockafellar: Convex Functions and Dual Extremum Problems, Ph.D. Thesis, Department of Mathematics, Havard University, Cambridge (1963).Google Scholar
  15. R. T. Rockafellar: Minimax theorems and conjugate saddle-functions, Math. Scand. 14 (1964) 151–173.https://doi.org/10.7146/math.scand.a-10714Google Scholar
  16. R. T. Rockafellar: Duality theorems for convex functions, Bull. Amer. Math. Soc. 70 (1964) 189-192.https://doi.org/10.1090/S0002-9904-1964-11074-0Google Scholar
  17. R. T. Rockafellar: Convex Analysis, Princeton University Press, Princeton (1970).https://doi.org/10.1515/9781400873173Google Scholar

Suggested citation

H. Martini, N. M. Nam, A. Robinson. “On the Equivalence of the Theorems of Helly, Radon, and Carathéodory via Convex Analysis.” Journal of Convex Analysis 22 (2015), No. 2, 591–601. https://doi.org/10.68381/jca22029

Download BibTeXPublished by Heldermann Verlag.

Published by Heldermann Verlag, 2015. Rights now held by Banach Press LLC.