pith. sign in

arxiv: 2603.11107 · v2 · pith:PKARYV6Xnew · submitted 2026-03-11 · 🧮 math.OC · math.CO

From Computational Certification to Exact Coordinates: Heilbronn's Triangle Problem on the Unit Square Using Mixed-Integer Optimization

Nathan Sudermann-Merx This is my paper

Pith reviewed 2026-05-22 10:56 UTC · model grok-4.3

classification 🧮 math.OC math.CO
keywords Heilbronn triangle problemmixed-integer nonlinear programmingsymmetry breakingnumerical certificationexact coordinatesunit squarecombinatorial geometryglobal optimization
0
0 comments X

The pith

A mixed-integer nonlinear program with boundary symmetry breaking recovers exact coordinates for all best-known Heilbronn triangle configurations up to nine points.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops a mixed-integer nonlinear programming approach to Heilbronn's triangle problem, which asks for the placement of n points in the unit square that maximizes the smallest area of any triangle formed by three points. A symmetry-breaking strategy based on boundary structure strengthens the model enough to compute an epsilon-globally optimal point for n=9 in 15 minutes on ordinary hardware. Numerical certification of the solution is then combined with exact symbolic computation to produce precise algebraic coordinates that match every previously reported best configuration for n up to 9, including the 2002 configuration of Comellas and Yebra. An examination of these exact placements shows that the areas of the non-critical triangles cluster tightly around only a few distinct values, which the authors interpret as evidence of rich underlying algebraic structure.

Core claim

The central claim is that a suitably strengthened mixed-integer nonlinear program can be solved to epsilon-global optimality for small n and that the resulting numerical points can be certified and then converted, via exact symbolic computation, into algebraic coordinates that coincide with all known optimal configurations for n ≤ 9.

What carries the argument

Mixed-integer nonlinear programming formulation strengthened by symmetry-breaking constraints derived from boundary structure, followed by numerical certification and exact symbolic recovery of coordinates.

If this is right

  • For n=9 an epsilon-globally optimal solution is obtained in 15 minutes rather than the previously reported one day of computation.
  • Exact algebraic coordinates are recovered for every best-known configuration with n ≤ 9.
  • Non-critical triangle areas in the optimal placements cluster around a small number of distinct numerical values.
  • The clustering pattern indicates the presence of rich algebraic relations among the coordinates.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same certification-plus-symbolic-recovery pipeline could be applied to other small-n instances of Heilbronn-type problems once the MINLP is solved.
  • The observed clustering of areas around few values suggests that optimal point sets may satisfy low-degree algebraic equations that could be solved directly without optimization.
  • Public release of the code and data makes it straightforward to test whether the method scales to n=10 or n=11 with additional computing time.

Load-bearing premise

The symmetry-breaking strategy based on boundary structure yields a substantially stronger model that still contains all globally optimal configurations without excluding them.

What would settle it

Finding a point set for any n ≤ 9 whose smallest triangle area is strictly smaller than the value obtained from the certified solution, or obtaining algebraic coordinates for n=9 that differ from the Comellas-Yebra configuration.

Figures

Figures reproduced from arXiv: 2603.11107 by Nathan Sudermann-Merx.

Figure 1
Figure 1. Figure 1: Best-known values of ∆n for the Heilbronn problem in the unit square compared with the asymptotic upper bound n −8/7−1/2000 of Cohen, Pohoata, and Zakharov [7]. 1.3 Lower bounds A simple lower bound of order c/n3 for ∆n can be obtained as follows. Without regard to the unit-square constraint, consider the n points (i, i2 ) for i = 0, . . . , n−1. No three of these points are collinear, and hence every tria… view at source ↗
Figure 2
Figure 2. Figure 2: Symmetry breaking used in the optimization model. [PITH_FULL_IMAGE:figures/full_fig_p011_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: The colored boxes highlight the individual enhancement groups; the core model [PITH_FULL_IMAGE:figures/full_fig_p011_3.png] view at source ↗
Figure 3
Figure 3. Figure 3: The final mixed-integer formulation P ⋆ ∆. Colored boxes indicate the core model P 0 ∆ (blue) and the enhancements: product substitution (teal), sign fixing (orange), symmetry break￾ing (red), and variable domains (gray). 3.5 Comparison with Monji, Modir and Kocuk The concurrent work of Monji, Modir and Kocuk [17] was the first to formulate the Heilbronn problem as a mixed-integer nonlinear problem and to … view at source ↗
Figure 4
Figure 4. Figure 4: Methodological pipeline of the paper: global computational certification (Step 1), ex [PITH_FULL_IMAGE:figures/full_fig_p014_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Optimal configuration for n = 7 with its eight critical triangles highlighted. Step 2: Exact analytical refinement Guided by these observations, we set up a parametric ansatz. The boundary structure fixes seven coordinates (x1 = 0, y2 = 0, x3 = 1, x4 = y4 = 1, x5 = 0, y5 = 1), and the shared x-coordinate of p2 and p7 introduces an additional coupling, leaving six unknowns a, b, c, d, e, f ( [PITH_FULL_IMA… view at source ↗
Figure 6
Figure 6. Figure 6: Optimal configuration for n = 5. 17 [PITH_FULL_IMAGE:figures/full_fig_p017_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Optimal configuration for n = 6. 5.3 n = 7: Eight critical triangles, H⋆ 7 = f − 1 2 The detailed derivation for n = 7 is given in Section 4.3. The configuration has eight critical triangles, and the exact coordinates are parameterized by the root of 19f 3 − 27f 2 + 11f − 1 near 0.5839, yielding H⋆ 7 ≈ 0.08386. Pt x y 1 0 19f 2 − 16f + 3 2 19f 2 − 27f + 10 0 3 1 −19f 2+10f+1 2 4 1 1 5 0 1 6 −19f 2 + 8f + 2… view at source ↗
Figure 8
Figure 8. Figure 8: Optimal configuration for n = 7. 5.4 n = 8: Twelve critical triangles, H⋆ 8 = − 1 36 + √ 13 36 The configuration exhibits a point-symmetric structure with twelve critical triangles and a unique optimal solution involving √ 13. 18 [PITH_FULL_IMAGE:figures/full_fig_p018_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: Optimal configuration for n = 8. 5.5 n = 9: Eleven critical triangles, H⋆ 9 = − 11 64 + 9 √ 65 320 The configuration has eleven critical triangles and is invariant under reflection in the anti￾diagonal (x, y) 7→ (1 − y, 1 − x). The unique optimal solution involves √ 65. Pt x y 1 0 1 − √ 65 10 2 3 8 − √ 65 40 0 3 1 9 16 − 3 √ 65 80 4 3 8 − √ 65 40 1 5 0 5 8 + √ 65 40 6 1 4 + √ 65 20 3 4 − √ 65 20 7 7 16 + 3… view at source ↗
Figure 10
Figure 10. Figure 10: Optimal configuration for n = 9. 6 Further observations and research questions 6.1 Growth of the number of critical triangles A structural feature of the optimal configurations worth noting is the number of critical triangles, i.e., triangles whose area equals the minimum [PITH_FULL_IMAGE:figures/full_fig_p019_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: Critical triangles as a function of n. Any such bound would have implications for the structure of the polynomial systems that arise in Step 2 of the framework, since each critical triangle contributes an equality constraint. Even a linear lower bound of the form Ω(n) would be significant, as it would guarantee that optimal configurations are constrained by at least as many active area equalities as there… view at source ↗
Figure 12
Figure 12. Figure 12: Degeneracy plot for [PITH_FULL_IMAGE:figures/full_fig_p020_12.png] view at source ↗
read the original abstract

We develop a mixed-integer nonlinear programming (MINLP) approach for the classical Heilbronn triangle problem, demonstrating the capability of modern global optimization solvers to tackle challenging combinatorial geometry problems. A symmetry-breaking strategy based on boundary structure yields a substantially stronger model: for $n=9$, we compute an $\varepsilon$-globally optimal point in 15 minutes on a standard desktop computer, improving upon the previously reported effort of approximately one day. By combining numerical certification with exact symbolic computation, we recover exact coordinates matching all best-known configurations for $n\le 9$, including the $n=9$ configuration of Comellas and Yebra (2002). An analysis of these configurations reveals the clustering of noncritical triangle areas around a small number of distinct values, suggesting rich underlying algebraic structure. All code and data are publicly available.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 3 minor

Summary. The manuscript develops a mixed-integer nonlinear programming (MINLP) approach to Heilbronn's triangle problem on the unit square. It introduces a symmetry-breaking strategy based on boundary structure to strengthen the model, enabling faster computation of ε-globally optimal points. For n=9, it achieves this in 15 minutes, and combines numerical certification with exact symbolic computation to recover exact coordinates matching all best-known configurations for n ≤ 9, including that of Comellas and Ybera (2002). The paper also analyzes clustering of noncritical triangle areas and makes all code and data publicly available.

Significance. If the symmetry-breaking preserves all global optima and the certification is rigorous, this work is significant for demonstrating the applicability of modern global optimization techniques to a challenging problem in combinatorial geometry. It provides a substantial computational speed-up over prior efforts and recovers exact solutions, offering insights into the algebraic structure of optimal configurations through the observed clustering of areas. The public release of code and data is a clear strength that enhances reproducibility.

major comments (1)
  1. [§3] §3 (Symmetry-breaking strategy): The claim that the boundary-structure symmetry-breaking yields a substantially stronger model that still contains all globally optimal configurations lacks an explicit proof or exhaustive enumeration. It is asserted that every candidate point set can be rigidly transformed (without decreasing the minimal triangle area) into one obeying the chosen boundary ordering, but no verification is provided that this holds for all possible optima. This is load-bearing for the completeness of the recovered coordinates and the ε-global optimality claim.
minor comments (3)
  1. [Abstract and §1] The reference to Comellas and Yebra (2002) in the abstract and introduction should be expanded with full bibliographic details and page numbers in the reference list.
  2. [Table 1] Table 1 (computational results): The reported times and ε values would benefit from explicit mention of the hardware specifications and solver version used for reproducibility.
  3. [Figure 3] Figure 3 (area clustering): The plot would be clearer with an accompanying table listing the distinct area values and their multiplicities for each n.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading and constructive feedback on our manuscript. We address the single major comment below and will revise the paper to strengthen the justification for the symmetry-breaking approach.

read point-by-point responses

  1. Referee: [§3] §3 (Symmetry-breaking strategy): The claim that the boundary-structure symmetry-breaking yields a substantially stronger model that still contains all globally optimal configurations lacks an explicit proof or exhaustive enumeration. It is asserted that every candidate point set can be rigidly transformed (without decreasing the minimal triangle area) into one obeying the chosen boundary ordering, but no verification is provided that this holds for all possible optima. This is load-bearing for the completeness of the recovered coordinates and the ε-global optimality claim.

    Authors: We thank the referee for highlighting this point. The boundary-structure symmetry-breaking is based on ordering points according to their positions on the boundary of the unit square (e.g., prioritizing points on specific edges in a cyclic manner) to eliminate equivalent configurations under the square's symmetries. We acknowledge that the current manuscript asserts this transformation preserves all global optima without providing a self-contained formal proof or exhaustive enumeration for arbitrary n. In the revised manuscript we will add a dedicated paragraph in §3 that rigorously justifies the claim: any finite point set in the unit square admits a rigid motion (rotation by a multiple of 90 degrees combined with reflection if needed) that maps it to a configuration satisfying the chosen boundary ordering while leaving the minimal triangle area unchanged, because the objective function is invariant under isometries and the domain is symmetric. We will also include a small-scale exhaustive verification for n ≤ 5 by comparing solutions with and without the symmetry-breaking constraints. This revision will directly support the completeness of the recovered coordinates and the ε-global optimality statements. revision: yes

Circularity Check

0 steps flagged

No significant circularity in the derivation chain

full rationale

The paper applies standard mixed-integer nonlinear programming to the externally defined Heilbronn triangle problem of maximizing minimal triangle area for n points in the unit square. The symmetry-breaking strategy based on boundary structure is introduced as a modeling enhancement that strengthens the formulation while asserted to retain all global optima, but this does not reduce any equation or claim to a self-referential definition or fitted input renamed as prediction. Exact coordinates are recovered via numerical certification followed by symbolic computation and shown to match independently published configurations (e.g., Comellas and Yebra 2002), providing external validation rather than internal closure. No load-bearing self-citation, uniqueness theorem imported from the authors, or ansatz smuggled via prior work appears in the derivation; the approach remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

1 free parameters · 1 axioms · 0 invented entities

The central claim depends on the MINLP formulation correctly encoding the minimal triangle area objective and on the solver returning certified near-global optima that can be lifted to exact algebraic values.

free parameters (1)
  • epsilon optimality tolerance
    The tolerance used to declare an epsilon-globally optimal point for n=9.
axioms (1)
  • domain assumption The Heilbronn triangle problem admits an exact mixed-integer nonlinear programming formulation whose feasible set includes all candidate point placements.
    The paper builds the entire approach on this modeling assumption.

pith-pipeline@v0.9.0 · 5672 in / 1285 out tokens · 59964 ms · 2026-05-22T10:56:27.139950+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Out-of-the-Box Global Optimization for Packing Problems: New Models and Improved Solutions

    math.OC 2026-05 unverdicted novelty 7.0

    New nonlinear formulations for geometric packing problems, solved with FICO Xpress and SCIP, produce improved and first-known solutions for several variants.

Reference graph

Works this paper leans on

24 extracted references · 24 canonical work pages · cited by 1 Pith paper

  1. [1]

    Mixed- integer nonlinear optimization

    P. Belotti, C. Kirches, S. Leyffer, J. Linderoth, J. Luedtke, and A. Mahajan. “Mixed- integer nonlinear optimization”. In:Acta Numerica22 (2013), pp. 1–131

    work page 2013

  2. [2]

    Berthold, D

    T. Berthold, D. Kamp, G. Mexi, S. Pokutta, and I. Pólik.Global Optimization for Com- binatorial Geometry Problems Revisited in the Era of LLMs. 2026

    work page 2026

  3. [3]

    An Algorithm for Heilbronn’s Problem

    C. Bertram–Kretzberg, T. Hofmeister, and H. Lefmann. “An Algorithm for Heilbronn’s Problem”. In:SIAM Journal on Computing30.2 (2000), pp. 383–390

    work page 2000

  4. [4]

    A brief history of linear and mixed-integer programming computation

    R. E. Bixby. “A brief history of linear and mixed-integer programming computation”. In:Optimization Stories. European Mathematical Society-EMS-Publishing House GmbH, 2012, pp. 107–121

    work page 2012

  5. [5]

    Non-convex mixed-integer nonlinear programming: a sur- vey

    S. Burer and A. N. Letchford. “Non-convex mixed-integer nonlinear programming: a sur- vey”. In:Surveys in Operations Research and Management Science17.2 (2012), pp. 97– 106

    work page 2012

  6. [6]

    Searching approximate global optimal Heilbronn configu- rations of nine points in the unit square via GPGPU computing

    L. Chen, Y. Xu, and Z. Zeng. “Searching approximate global optimal Heilbronn configu- rations of nine points in the unit square via GPGPU computing”. In:Journal of Global Optimization68.1 (2017), pp. 147–167

    work page 2017

  7. [7]

    Lower bounds for incidences

    A. Cohen, C. Pohoata, and D. Zakharov. “Lower bounds for incidences”. In:Inventiones Mathematicae240 (2025), pp. 713–752

    work page 2025

  8. [8]

    New lower bounds for Heilbronn numbers

    F. Comellas and J. L. A. Yebra. “New lower bounds for Heilbronn numbers”. In:The Electronic Journal of Combinatorics9.1 (2002), R6

    work page 2002

  9. [9]

    Conforti, G

    M. Conforti, G. Cornuéjols, and G. Zambelli.Integer Programming. Vol. 271. Graduate Texts in Mathematics. Springer, 2014

    work page 2014

  10. [10]

    Heilbronn’s problem of eight points in the square

    L. Dehbi and Z. Zeng. “Heilbronn’s problem of eight points in the square”. In:Journal of Systems Science and Complexity35.6 (2022), pp. 2452–2480

    work page 2022

  11. [11]

    Heilbronn Problem for Six Points in a Planar Convex Body

    A. W. M. Dress, L. Yang, and Z. Zeng. “Heilbronn Problem for Six Points in a Planar Convex Body”. In:Minimax and Applications. Ed. by D.-Z. Du and P. M. Pardalos. Boston, MA: Springer US, 1995, pp. 173–190

    work page 1995

  12. [12]

    Friedman.Packing Center.https : / / erich - friedman

    E. Friedman.Packing Center.https : / / erich - friedman . github . io / packing/. Ac- cessed: 2026-02-20. 21

    work page 2026

  13. [13]

    Maximizing the Smallest Triangle Made byNPoints in a Square

    M. Goldberg. “Maximizing the Smallest Triangle Made byNPoints in a Square”. In: Mathematics Magazine45.3 (1972), pp. 135–144

    work page 1972

  14. [14]

    On Heilbronn’s triangle problem

    J. Komlós, J. Pintz, and E. Szemerédi. “On Heilbronn’s triangle problem”. In:Journal of the London Mathematical Society. 2nd ser. 24.3 (1981), pp. 385–396

    work page 1981

  15. [15]

    A lower bound for Heilbronn’s problem

    J. Komlós, J. Pintz, and E. Szemerédi. “A lower bound for Heilbronn’s problem”. In: Journal of the London Mathematical Society. 2nd ser. 25.1 (1982), pp. 13–24

    work page 1982

  16. [16]

    Computability ofGlobalSolutionsto FactorableNonconvexPrograms: Part I — Convex Underestimating Problems

    G.P.McCormick. “Computability ofGlobalSolutionsto FactorableNonconvexPrograms: Part I — Convex Underestimating Problems”. In:Mathematical Programming10.1 (1976), pp. 147–175

    work page 1976

  17. [17]

    Monji, A

    A. Monji, A. Modir, and B. Kocuk.Solving the Heilbronn Triangle Problem using Global Optimization Methods. 2025

    work page 2025

  18. [18]

    On a Problem of Heilbronn

    K. F. Roth. “On a Problem of Heilbronn”. In:Journal of the London Mathematical Society s1-26.3 (1951), pp. 198–204

    work page 1951

  19. [19]

    On a problem of Heilbronn, II

    K. F. Roth. “On a problem of Heilbronn, II”. In:Proceedings of the London Mathematical Society. 3rd ser. 25.2 (1972), pp. 193–212

    work page 1972

  20. [20]

    On a problem of Heilbronn, III

    K. F. Roth. “On a problem of Heilbronn, III”. In:Proceedings of the London Mathematical Society. 3rd ser. 25.3 (1972), pp. 543–549

    work page 1972

  21. [21]

    On a problem of Heilbronn

    W. M. Schmidt. “On a problem of Heilbronn”. In:Journal of the London Mathematical Society. 2nd ser. 4.3 (1972), pp. 545–550

    work page 1972

  22. [22]

    L. A. Wolsey.Integer Programming. 2nd. John Wiley & Sons, 2021

    work page 2021

  23. [23]

    L. Yang, J. Zhang, and Z. Zeng.Heilbronn problem for five points. Tech. rep. 1991

    work page 1991

  24. [24]

    On the Heilbronn Optimal Configuration of Seven Points in the Square

    Z. Zeng and L. Chen. “On the Heilbronn Optimal Configuration of Seven Points in the Square”. In:Automated Deduction in Geometry. Ed. by T. Sturm and C. Zengler. Berlin, Heidelberg: Springer Berlin Heidelberg, 2011, pp. 196–224. A Best-known configurations for10≤n≤16 The best-known configurations for10≤n≤12are due to Comellas and Yebra [8] (forn= 10 andn= ...

    work page 2011