The Happy Ending problem: forcing convex polygons

Problem

Any set of \(2^{n-2} + 1\) points in the plane in general position contains a convex \(n\)-gon

Let \( g(n)\) be the smallest number such that any set of \( n\) points in general position contains a convex \( n\)-gon. Paul Erdösand George Szekeres proved upper [1] and lower [2] bounds:

\(\displaystyle 2^{n-2} + 1 \leq g(n) \leq \binom{2n-4}{n-2} + 1. \)

The upper bound has been improved several times, but the lower bound has not budged. It is correct for \( n \le 5\), and is conjectured to be exact.

Fan Chung and Ron Graham [1] made the first (albeit minor) improvement to the upper bound, showing \( g(n) \leq \binom{2n-4}{n-2}\).

Next, Kleitman and Pachter [3] improved this to \( g(n) \leq \binom{2n-4}{n-2} + 7 - 2n\).

Then Tóth and Valtr [4] improved this by about a factor of 2, showing \( g(n) \leq \binom{2n-5}{n-2} + 2\), which they later improved slightly [5] to \( g(n) \leq \binom{2n-5}{n-2} + 1\).

Bibliography
1 F. R. K. Chung and R. L. Graham, Forced convex \( n\)-gons in the plane, Discrete and Computational Geometry 19 (1998), 367-371.

1 P. Erdösand G. Szekeres, A combinatorial problem in geometry, Compositio Math. 2 (1935), 463-470.

2 P. Erdös, G. Szekeres: On some extremum problems in elementary geometry, Ann. Univ. Sci. Budapest. Eötvös Sect. Math. 3-4 (1960/1961), 53-62

3 D. J. Kleitman and L. Pachter, Finding convex sets among points on the plane, Discrete and Computational Geometry 19 (1998), 405-410.

4 G. T´oth and P. Valtr, “Note on the Erd˝os–Szekeres theorem”, Discrete Comput. Geom. 19:3, Special Issue (1998), 457–459.

5 Tóth, G., Valtr, P.: The Erdös-Szekeres theorem: upper bounds and related results. In: Goodman, J.E., Pach, J., Welzl, E. (eds.) Combinatorial and Computational Geometry. MSRI Publications, vol. 52, pp. 557–568. Cambridge University Press, Cambridge (2005)