The happy end problem, also called the "happy ending problem," is the problem of determining for 
the smallest number of points 
in general position
in the plane (i.e., no three of which are collinear),
such that every possible arrangement of 
points will always contain at
least one set of 
points that are the vertices
of a convex polygon of 
sides. The problem was so-named by Erdős when two investigators
who first worked on the problem, Ester Klein and George Szekeres, became engaged
and subsequently married (Hoffman 1998, p. 76).
Since three noncollinear points always determine a triangle, 
.
Random arrangements of 
points are illustrated above. Note that no convex quadrilaterals
are possible for the arrangements shown in the fifth and eighth figures above, so
must be greater than 4. E. Klein
proved that 
by showing that any arrangement of five points must fall
into one of the three cases (left top figure; Hoffman 1998, pp. 75-76).
Random arrangements of 
points are illustrated above.
Note that no convex pentagons are possible for the arrangement
shown in the fifth figure above, so 
must be greater than 8. E. Makai proved 
after demonstrating that a counterexample
could be found for eight points (right top figure; Hoffman
1998, pp. 75-76).
As the number of points 
increases, the number of k-subsets
of 
that must be examined to see if they form convex 
-gons increases as 
, so combinatorial explosion prevents cases much bigger
than 
from being easily studied. Furthermore, the parameter space becomes so large that
searching for a counterexample at random even
for the case 
with 
points takes an extremely long time. For these reasons, the
general problem remains open.
was demonstrated by Szekeres and
Peters (2006) using a 1500 CPU-hour computer search that eliminated all possible
configurations of 17 points
that lacked convex hexagons while examining only a tiny
fraction of all configurations. Marić (2019)
and Scheucher (2020) independently verified 
using satisfiability
(SAT) solving in a few CPU hours, a time later reduced to 10 CPU-minutes by Scheucher
(2023) and to 8.53 CPU-seconds by Heule and Scheucher (2024).
The first few values of 
for 
, 4, 5, and 6 are therefore 3, 5, 9, 17, which happen to
be exactly 
.
However, the values of 
for 
are unknown.
The lower bound construction of Erdős and Szekeres (1961) gives, for every 
, a point set of 
points in general
position containing no set of 
points that forms a convex
polygon. Examples with 8, 16, and 32 points containing
no convex polygon with 5, 6, and 7 vertices,
respectively, are illustrated above. The 32-point integer-coordinate
realization lies in a 
grid (Duque et al. 2018).
Combining this construction with the upper bound of Erdős and Szekeres (1935) gives
 |
(1)
|
where 
is a binomial coefficient. For 
, this has since been reduced to 
for
 |
(2)
|
by Chung and Graham (1998), 
for
 |
(3)
|
by Kleitman and Pachter (1998), and 
for
 |
(4)
|
by Tóth and Valtr (1998).
-gons
in the Plane." Discr. Comput. Geom. 19, 367-371, 1998.Duque,
F.; Fabila-Monroy, R.; and Hidalgo-Toscano, C. "Point Sets with Small Integer
Coordinates and no Large Convex Polygons." Discr. Comput. Geom. 59,
461-476, 2018.