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.

Figure 1: Examples showing that .

It is obvious that for , just three points in general position are sufficient to create a triangle. For , Paul Erdos and Esther Klein (later Szekeres) determined that at least five points are necessary, and Kalbfleisch later determined . Much later, George Szekeres (posthumously) and Lindsay Peters published a computer proof [6] that .

For higher , Erdos and George Szekeres in 1935 gave the upper bound

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

Bibliography

1

F. R. K. Chung and R. L. Graham, Forced convex -gons in the plane, Discrete Comput. Geom. 19 (1996), 229-233.

2

P. Erdos and G. Szekeres, A combinatorial problem in geometry, Compositio Math. 2 (1935), 463-470.

3

P. Erdos 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 Erdos-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 Erdos-Szekeres problem, ANZIAM J. 48 (2006), 151-164.

7

G. Tóth and P. Valtr, Note on the Erdos-Szekeres theorem, Discrete Comput. Geom. 19 (1998), 457-459.

8

G. Tóth and P. Valtr, The Erdos-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.