Improved upper bounds for the Heilbronn's Problem for $k$-gons
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914804076118016 |
|---|---|
| author | Gajjala, Rishikesh Ravi, Jayanth |
| author_facet | Gajjala, Rishikesh Ravi, Jayanth |
| contents | 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/2}\log{n})$ 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\geq 4$ points. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_12945 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Improved upper bounds for the Heilbronn's Problem for $k$-gons Gajjala, Rishikesh Ravi, Jayanth Discrete Mathematics Computational Geometry Combinatorics 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/2}\log{n})$ 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\geq 4$ points. |
| title | Improved upper bounds for the Heilbronn's Problem for $k$-gons |
| topic | Discrete Mathematics Computational Geometry Combinatorics |
| url | https://arxiv.org/abs/2405.12945 |