2024/05/21 by Rishikesh Gajjala, Gajjala, Rishikesh, Jayanth Ravi +1
Mathematics · #Analytic Number Theory Research #Combinatorics (math.CO) #Computational Geometry (cs.CG) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory #Mathematical Approximation and Integration
paper · pdf · doi:10.48550/arxiv.2405.12945
openalex publication_date 2024/05/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The Heilbronn triangle problem asks for the placement of n points in a unit square that maximizes the smallest area of a triangle formed by any three of those points. In 1972, Schmidt considered a natural generalization of this problem. He asked for the placement of n points in a unit square that maximizes the smallest area of the convex hull formed by any four of those points. He showed a lower bound of Ω(n-3/2), which was improved to Ω(n-3/2logn) by Leffman. A trivial upper bound of 3/n could be obtained, and Schmidt asked if this could be improved asymptotically. However, despite several efforts, no asymptotic improvement over the trivial upper bound was known for the last 50 years, and the problem started to get the tag of being notoriously hard. Szemerédi posed the question of whether one can, at least, improve the constant in this trivial upper bound. In this work, we answer this question by proving an upper bound of 2/n+o(1/n). We also extend our results to any convex hulls formed by k≥ 4 points.