|
The happy ending problem asks, for a given integer  , to find the smallest number  of points laid on a plane in general position such that a subset of  points can be made the vertices of a convex  -agon.
It is obvious that for  , just three points in general position are sufficient to create a triangle. For  , Paul Erdős and Esther Klein (later Szekeres) determined that at least five points are necessary, and Kalbfleisch later determined  . Much later, George Szekeres and Lindsay Peters reckoned  but the paper remains unpublished today.
For higher  , Erdős and George Szekeres in 1935 gave the upper bound
. Later, in 1961 they gave the lower bound
 .
New ideas for the upper bound were in the air in the late 1990s, with Chung and Graham showing that if  , then
   
- 1
- F. R. K. Chung and R. L. Graham, Forced convex
 -gons in the plane, Discrete Comput. Geom. 19 (1996), 229-233.
- 2
- P. Erdős and G. Szekeres, A combinatorial problem in geometry, 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
- G. Tóth and P. Valtr, Note on the Erdős-Szekeres theorem, Discrete Comput. Geom. 19 (1998), 457-459.
- 7
- 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.
|
