Happy End Problem

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 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 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 -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 become 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 computer search which eliminated all possible configurations of 17 points which lacked convex hexagons while examining only a tiny fraction of all configurations.