Heilbronn triangle problem in the unit square

# Heilbronn triangle problem in the unit square ## Goal Place `n` points in the closed unit square `[0, 1]^2` so that the smallest triangle spanned by any three of them has the largest possible area. Heilbronn's problem (1950s) asks how this maximum, `H(n)`, decays with `n`; here the task is the finite one: for each `n` build a configuration whose smallest triangle is as large as, or larger than, the best one known. Instances are `n = 10, 11, ..., 20`. Optimal configurations are proven for `n <= 9` (5: Yang, Zhang & Zeng 1991; 6: Dress, Yang & Zeng 1995; 7: Chen & Chen 2011; 8: Dehbi & Zeng 2022; 9: Sudermann-Merx, March 2026); every instance here is open. `heilbronn.py` exposes place(n: int, time_budget: float, seed: int) -> list[tuple[number, number]] returning exactly `n` points `(x, y)` with `0 <= x, y <= 1`. A coordinate may be an int, a float, or an integer pair `(p, q)` meaning the exact rational `p/q` (the `fractions` module is not on the import allowlist, so this is how you hand over exact rationals; `(2, 31)` is `2/31`). Every value is converted to an exact rational (a float is a binary fraction, nothing is rounded), so a solver that finishes with an exact rational refinement is scored exactly. ## Metric metric = mean over n of min_area(n) / record(n) The eval recomputes the smallest area over all `C(n, 3)` triangles in integer arithmetic on a common denominator; nothing the solver reports is used. A configuration with three collinear (or coincident) points scores 0 on that instance; points outside the square, a repeated point or a wrong count fail the run (`wrong_answer`). `ZT_EVAL_SEED` only changes the `seed` handed to `place`; the instance set is fixed. ## Records Best-known values from Erich Friedman's Packing Center, "The Heilbronn Problem for Squares" (https://erich-friedman.github.io/packing/heilbronn/), read 2026-09-07, cross-checked with MathWorld's closed forms and the coordinate tables in arXiv:2603.11107 (Appendix A). None is proven optimal. | n | best known | exact? | source | |---|---|---|---| | 10 | 0.0465374195825... | yes, root of `3456x^3 - 1764x^2 + 268x - 9` | Comellas & Yebra, Electron. J. Combin. 9 (2002) R6 | | 11 | 1/27 = 0.037037... | yes | Goldberg 1972 | | 12 | 0.0325988586918... | yes, root of `64x^3 + 80x^2 + 28x - 1` | Comellas & Yebra | | 13 | 0.02702+ | page precision | Karpov, Aug 2011 | | 14 | 0.0243039796209... | yes, root of `320x^3 + 768x^2 - 60x + 1` | Beyleveld, Aug 2006 | | 15 | 0.02121+ | page precision | Sudermann-Merx, Aug 2026 (previous 0.02111) | | 16 | 7/341 = 0.0205278... | yes, rational coordinates | Beyleveld, Aug 2006 | | 17 | 0.016481+ | page precision | Stead, Jul 2026 | | 18 | 0.01498+ | page precision | Stead, Aug 2026 | | 19 | 0.01394+ | page precision | Stead, Aug 2026 | | 20 | 0.01291+ | page precision | Shanley, Jul 2026 | "Page precision" rows are copied with the digits Friedman prints; the true record lies within one unit of the last digit (`record_unit` in the eval output). The ratio is taken against the printed value, so it can exceed 1.0 by up to that unit without a new record; `records_beaten` lists an `n` only when your area exceeds `record + unit`. Friedman's page continues to `n = 35`; those rows were all set in July-August 2026 and can be added later. ## Constraints - Standard library only (`math`, `random`, `itertools`, `functools`, `collections`, `heapq`, `time`). The eval rejects other imports. - Respect `time_budget` (seconds, per call). The default is 10 s per instance, about 110 s for a full eval; verification is negligible (1140 triangles at `n = 20`). - Deterministic given `seed`: use `random.Random(seed)`. ## Iterating quickly - `ZT_EVAL_INSTANCES` is a comma-separated subset of `10,...,20`; the full set is the default. - `ZT_EVAL_PER_INSTANCE_SECONDS` is the budget handed to `place` per instance (default 10). ``` ZT_EVAL_INSTANCES=10,16 ZT_EVAL_PER_INSTANCE_SECONDS=3 python eval.py ``` ## Ideas that are known to matter (check the journal before repeating one) - **It is a max-min problem with few active triangles.** At a good configuration many triangles tie at the minimum. Moving one point changes only the `C(n-1, 2)` triangles through it, so an incremental "raise the worst triangle" climb is cheap; the baseline does exactly that with random restarts and a shrinking step. - **Points sit on the boundary and use symmetry.** Every record has several points on the sides of the square; Comellas-Yebra's `n = 10` and `n = 12` are symmetric about both diagonals, `n = 14` about both axes, `n = 16` and `n = 20` under a half turn, while the newest records (`n = 13, 15, 17, 18, 19`) are asymmetric. Search a symmetric family first (few free parameters), then break the symmetry. - **Polish continuously.** Once the active triangles are known, the optimum is a vertex of a small system: maximise `t` subject to `area(i, j, k) >= t` for the active triples. Successive linear programmes / Newton steps on the active set converge quadratically; the records are algebraic numbers for that reason (`n = 10, 12, 14` are cubic irrationals, `n = 16` is rational). - **Global methods that produced records:** simulated annealing on the min area (Comellas-Yebra), and, in 2025-26, mixed-integer nonlinear programming with symmetry breaking and boundary occupancy constraints (Monji, Modir & Kocuk, arXiv:2512.14505; Sudermann-Merx, arXiv:2603.11107), which certified `n = 9` and reproduced `n = 10`. - **Finish exactly.** Rounding a good float configuration to a nearby rational grid (or to the exact algebraic solution of the active system) costs nothing in the score and makes the hub's re-verification identical to yours. Write one honest line in `NOTES.md`: the idea, and which `n` it helped. Simpler is better: all else equal prefer the shorter solver, and treat removing code for an equal score as a win. Log every experiment, including discards, in your results.tsv.