Happy Ending: An Empty Hexagon in Every Set of 30 Points
Tools and Algorithms for the Construction and Analysis of Systems Lecture Notes in Computer Science(2024)
摘要
Satisfiability solving has been used to tackle a range of long-standing open
math problems in recent years. We add another success by solving a geometry
problem that originated a century ago. In the 1930s, Esther Klein's exploration
of unavoidable shapes in planar point sets in general position showed that
every set of five points includes four points in convex position. For a long
time, it was open if an empty hexagon, i.e., six points in convex position
without a point inside, can be avoided. In 2006, Gerken and Nicolás
independently proved that the answer is no. We establish the exact bound: Every
30-point set in the plane in general position contains an empty hexagon. Our
key contributions include an effective, compact encoding and a search-space
partitioning strategy enabling linear-time speedups even when using thousands
of cores.
更多查看译文
AI 理解论文
溯源树
样例
生成溯源树,研究论文发展脉络
Chat Paper
正在生成论文摘要