Every 30 points contain an empty hexagon
A set of points in the plane is in general position if no three lie on a line. An empty hexagon in such a set is a convex hexagon whose vertices are points of the set and which contains no other point of the set. Find the smallest such that every points in general position contain an empty hexagon.
History and references
Solved in 2024 by Marijn Heule and Manfred Scheucher.
In the 1930s Esther Klein showed that any 5 points in general position include 4 in convex position, which started a long study of unavoidable shapes in point sets. Large enough sets always contain empty convex quadrilaterals and pentagons, but there are arbitrarily large sets with no empty convex heptagon. Whether empty hexagons can be avoided stayed open for a long time, until Gerken and Nicolás independently proved around 2006 that they cannot. Overmars had found a set of 29 points with no empty hexagon in 2003. In 2024 Heule and Scheucher closed the gap with a SAT solver, proving that every 30 points in general position contain an empty hexagon, so the answer is 30.
References
Solutions 0
Sign in or create an account to publish a solution