Heilbronn's triangle problem
Heilbronn's triangle problem in the unit square: configurations of 11 to 16 points, every one checked in exact arithmetic

| 1 | # Heilbronn's triangle problem |
| 2 | |
| 3 | Place $n$ points in the unit square so that the smallest triangle spanned by any three of them is as large as possible: |
| 4 | |
| 5 | $$\Delta(n) = \max_{P \subset [0,1]^2,\ |P| = n}\ \min_{\{a,b,c\} \subseteq P} \operatorname{area}(a,b,c)$$ |
| 6 | |
| 7 | Points may lie on the boundary. Three points on a line span a triangle of area 0, so a good configuration has no three collinear points. The problem is Hans Heilbronn's and first appeared in print in Roth (1951). |
| 8 | |
| 9 | **Goal here.** Configurations of $n = 11, \dots, 16$ points whose smallest triangle is as large as the best known one, or larger. Every configuration pushed here is checked in exact arithmetic by [verify.py](verify.py). |
| 10 | |
| 11 | ## What is known |
| 12 | |
| 13 | Values are cut to ten decimals, as the check prints them. As of 2026-11-10. |
| 14 | |
| 15 | | $n$ | $\Delta(n) \ge$ | found by, and what is proven | |
| 16 | |---|---|---| |
| 17 | | 5 | 0.1924500897 | optimal: Yang, Zhang, Zeng (1991) | |
| 18 | | 6 | 0.125 | Goldberg (1972); optimal: Dress, Yang, Zeng (1995) | |
| 19 | | 7 | 0.0838590090 | Comellas, Yebra (2002); optimal: Zeng, Chen (2011) | |
| 20 | | 8 | 0.0723764243 | Comellas, Yebra (2002); optimal: Dehbi, Zeng (2022) | |
| 21 | | 9 | 0.0548759991 | Comellas, Yebra (2002); optimal within a solver's tolerances, no rigorous proof: Monji, Modir, Kocuk (2025), Sudermann-Merx (2026) | |
| 22 | | 10 | 0.0465374195 | Comellas, Yebra (2002); optimal within a solver's tolerances, no rigorous proof: Sudermann-Merx (2026) | |
| 23 | | **11** | **0.0370370370** | Goldberg (1972); best known | |
| 24 | | **12** | **0.0325988586** | Comellas, Yebra (2002); best known | |
| 25 | | **13** | **0.0270199166** | Karpov (2011); best known, not formally published | |
| 26 | | **14** | **0.0243039796** | Beyleveld (2006); best known, not formally published | |
| 27 | | **15** | **0.0212105410** | Sudermann-Merx (August 2026); best known, replaced Karpov (2011) | |
| 28 | | **16** | **0.0205278592** | Beyleveld (2006); best known, not formally published | |
| 29 | |
| 30 | - For $n \ge 11$ nothing is proven beyond these constructions: no optimality certificate of any kind, and no upper bound close to them. |
| 31 | - Exact values: $\sqrt3/9$, $1/8$, $(\sqrt{13}-1)/36$ and $(9\sqrt{65}-55)/320$ for $n = 5, 6, 8, 9$; $1/27$ for $n = 11$ and $7/341$ for $n = 16$; for $n = 12$ and $n = 14$ the smallest positive roots of $64x^3 + 80x^2 + 28x - 1$ and $320x^3 + 768x^2 - 60x + 1$. |
| 32 | - For $n = 13$ the value is that of Karpov's arrangement with fully converged coordinates; the coordinates he published give 0.0270192722. |
| 33 | - Asymptotically, $(\log n)/n^2 \lesssim \Delta(n)$ (Komlós, Pintz, Szemerédi 1982) and $\Delta(n) \le n^{-7/6+o(1)}$ (Cohen, Pohoata, Zakharov 2024). |
| 34 | - Not this problem: AlphaEvolve's Heilbronn results of 2025 ($0.0365$ for 11 points; $0.0309$ and $0.0278$ for 13 and 14) are for a triangle and for convex regions of unit area. On the unit square it "did not manage to beat any of the records" (Georgiev, Gómez-Serrano, Tao, Wagner 2025, section 29). |
| 35 | |
| 36 | **Why 11 to 16.** Below 11 nothing is left to find by construction: $n \le 8$ is proven, and $n = 9, 10$ are certified numerically. From 11 on every case is undecided, and up to 16 each has a best known value with public coordinates, so a result here can be compared at once. Five of the six have stood for fifteen years or more; the sixth, $n = 15$, fell to a heuristic search in August 2026. Beyond 16 the records were all set since August 2026 and still change; those cases open here once their table settles. |
| 37 | |
| 38 | ## What counts as progress |
| 39 | |
| 40 | 1. **A first checked value** for an instance: any configuration the check accepts. |
| 41 | 2. **A higher checked value** than the best one this project has for an instance. |
| 42 | 3. **A reproduction**: a checked value equal to the best known one, to the check's ten decimals. It puts the literature's number under this project's own check, and is labelled a reproduction. |
| 43 | 4. **A new record**: a checked value above the best known one. The maintainers compare it with the record table before anyone calls it a record; it then belongs on that table too, which takes pull requests. |
| 44 | |
| 45 | Upper bounds and optimality proofs are not checked here. |
| 46 | |
| 47 | ## How to take part |
| 48 | |
| 49 | 1. Clone the project and run the check on the example: `python3 verify.py examples/`. |
| 50 | 2. Pick an open issue and start a branch of your own from `main`; a branch is a route, with its own folder `routes/<branch>/`. |
| 51 | 3. Put your notes in `routes/<branch>/README.md` and your configuration in `routes/<branch>/n<N>.txt`: $N$ lines `x y`, decimals or fractions. |
| 52 | 4. Push. The `verify` check answers on your commit, usually within seconds: `n = N: value`, or what to fix. |
| 53 | 5. Open a pull request into `main` when the result should stay; the maintainers merge. |
| 54 | |
| 55 | Agents: [AGENTS.md](AGENTS.md) has the exact commands and the rules. |
| 56 | |
| 57 | ## The check |
| 58 | |
| 59 | `verify.py` reads `n11.txt` … `n16.txt` directly in the route's folder, takes every coordinate as the exact rational it is written as, computes the area of all $\binom{n}{3}$ triangles and reports the smallest. It needs Python 3 and nothing else. |
| 60 | |
| 61 | - It fails, naming the file and the line, on a line that is not two numbers, a wrong number of points for the file's name, a point outside the square, a repeated point, and three points on one line. |
| 62 | - Any other `.txt` file is named in the log as ignored and never counts. A push without a configuration passes with "Nothing to check yet", which is not a result. |
| 63 | - [examples/n11.txt](examples/n11.txt) is an example of the format, not a record: 11 points found in a few seconds by [examples/search.py](examples/search.py), with smallest triangle $0.0321993507$. |
| 64 | |
| 65 | ## Sources |
| 66 | |
| 67 | - The record table for the unit square, kept by Tej Stead, continuing Erich Friedman's Packing Center: <https://math.tejstead.com/heilbronn/square/> (coordinates for every $n$, verified in exact arithmetic). |
| 68 | - M. Goldberg, Maximizing the smallest triangle made by N points in a square, *Mathematics Magazine* 45 (1972) 135–144. |
| 69 | - F. Comellas, J. L. A. Yebra, New lower bounds for Heilbronn numbers, *Electronic Journal of Combinatorics* 9 (2002) #R6: <https://www.combinatorics.org/ojs/index.php/eljc/article/view/v9i1r6>. |
| 70 | - N. Sudermann-Merx, From global optimization to exact coordinates: Heilbronn's triangle problem on the unit square, arXiv:2603.11107 (version 3, October 2026), with the best known configurations for $11 \le n \le 16$ in its appendix B and at <https://github.com/spiralulam/heilbronn>. |
| 71 | - A. Monji, A. Modir, B. Kocuk, Solving the Heilbronn triangle problem using global optimization methods, arXiv:2512.14505 (2025). |
| 72 | - Z. Zeng, L. Chen, On the Heilbronn optimal configuration of seven points in the square, *Automated Deduction in Geometry*, Springer (2011) 196–224. L. Dehbi, Z. Zeng, Heilbronn's problem of eight points in the square, *Journal of Systems Science and Complexity* 35 (2022) 2452–2480. |
| 73 | - A. Cohen, C. Pohoata, D. Zakharov, Lower bounds for incidences, arXiv:2409.07658 (2024). J. Komlós, J. Pintz, E. Szemerédi, A lower bound for Heilbronn's problem, *Journal of the London Mathematical Society* 25 (1982) 13–24. |
| 74 | - B. Georgiev, J. Gómez-Serrano, T. Tao, A. Z. Wagner, Mathematical exploration and discovery at scale, arXiv:2511.02864 (2025). A. Novikov et al., AlphaEvolve: a coding agent for scientific and algorithmic discovery, arXiv:2506.13131 (2025). |