happy ending problem

The happy ending problemMathworldPlanetmath asks, for a given integer n>2, to find the smallest number g(n) of points laid on a plane in general position such that a subset of n points can be made the vertices of a convex n-agon.

Figure 1: Examples showing that g(4)5.

It is obvious that for n=3, just three points in general position are sufficient to create a triangleMathworldPlanetmath. For n=4, Paul Erdős and Esther Klein (later Szekeres) determined that at least five points are necessary, and Kalbfleisch later determined g(5)=9. Much later, George Szekeres (posthumously) and Lindsay Peters published a computer proof [6] that g(6)=17.

For higher n, Erdős and George Szekeres in 1935 gave the upper bound


Later, in 1961 they gave the lower bound g(n)1+2n-2.

New ideas for the upper bound were in the air in the late 1990s, with Chung and Graham showing that if n4, then


while Kleitman and Pachter showed that then


And Géza Tóth and Pavel Valtr in 1998 gave the upper bound


which in 2005 they refined to



  • 1 F. R. K. Chung and R. L. Graham, Forced convex n-gons in the plane, Discrete Comput. Geom. 19 (1996), 229–233.
  • 2 P. Erdős and G. Szekeres, A combinatorial problem in geometryMathworldPlanetmathPlanetmath, Compositio Math. 2 (1935), 463–470.
  • 3 P. Erdős and G. Szekeres, On some extremum problems in elementary geometry, Ann. Univ. Sci. Budapest Eötvös Sect. Math. 3–4 (1961), 53–62.
  • 4 D. Kleitman and L. Pachter, Finding convex sets among points in the plane, Discrete Comput. Geom. 19 (1998), 405–410.
  • 5 W. Morris and V. Soltan, The Erdős-Szekeres problem on points in convex position – a survey, Bull. Amer. Math. Soc. 37 (2000), 437–458.
  • 6 L. Peters and G. Szekeres, Computer solution to the 17-point Erdős-Szekeres problem, ANZIAM J. 48 (2006), 151–164.
  • 7 G. Tóth and P. Valtr, Note on the Erdős-Szekeres theoremMathworldPlanetmath, Discrete Comput. Geom. 19 (1998), 457–459.
  • 8 G. Tóth and P. Valtr, The Erdős-Szekeres theorem: upper bounds and related results. Appearing in J. E. Goodman, J. Pach, and E. Welzl, eds., Combinatorial and computational geometry, Mathematical Sciences Research Institute Publications 52 (2005) 557–568.
Title happy ending problem
Canonical name HappyEndingProblem
Date of creation 2013-03-22 16:16:21
Last modified on 2013-03-22 16:16:21
Owner PrimeFan (13766)
Last modified by PrimeFan (13766)
Numerical id 13
Author PrimeFan (13766)
Entry type Definition
Classification msc 51D20
Synonym happy end problem