Happy Ending Problem - Empty Polygons

Empty Polygons

One may also consider the question of whether any sufficiently large set of points in general position has an empty quadrilateral, pentagon, etc., that is, one that contains no other input point. The original solution to the Happy Ending problem can be adapted to show that any five points in general position have an empty convex quadrilateral, as shown in the illustration, and any ten points in general position have an empty convex pentagon. However, there exist arbitrarily large sets of points in general position that contain no empty heptagon.

For a long time the question of the existence of empty hexagons remained open, but Nicolás (2007) and Gerken (2008) proved that every sufficiently large point set in general position contains a convex empty hexagon. More specifically, Gerken showed that the number of points needed is no more than f(9) for the same function f defined above, while Nicolás showed that the number of points needed is no more than f(25). Valtr (2006) supplies a simplification of Gerken's proof that however requires more points, f(15) instead of f(9). At least 30 points are needed: there exists a set of 29 points in general position with no empty convex hexagon.