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

Imagine you are a city planner tasked with placing $n$ new parks inside a perfect, square city block. Your goal isn't just to place them anywhere; you want to arrange them so that no three parks form a tiny, useless triangle. In fact, you want to make the smallest triangle formed by any three parks as large as possible.

This is the Heilbronn Triangle Problem. It sounds simple, but as you add more parks, the math gets incredibly messy. For decades, mathematicians could guess the best arrangements, but proving they were truly the best (and finding the exact coordinates) was like trying to solve a Rubik's cube while blindfolded.

This paper by Nathan Sudermann-Merx is like a master locksmith who finally found the key to open the lock for small city sizes ( $n=5$ to $n=9$ ). Here is how they did it, explained in everyday terms.

1. The Problem: The "Tiny Triangle" Nightmare

Imagine you have 9 dots on a piece of paper. You connect every possible trio of dots to make triangles. Some triangles will be huge; some will be microscopic. The "Heilbronn number" is the size of the smallest triangle you can make.

The goal is to move the dots around until that smallest triangle is as big as it can possibly be.

The Old Way: Previous attempts were like trying to find a needle in a haystack by searching the whole haystack blindly. For $n=9$ , it took a supercomputer cluster 125 days (or at least a full day on a modern machine) to get a "good guess" that was likely correct, but not mathematically proven.

2. The New Strategy: "Optimize-Then-Refine"

The author introduces a two-step process, which we can call "The Rough Draft and The Final Polish."

Step 1: The Rough Draft (The "Smart Search")

Instead of searching blindly, the author built a digital detective (a Mixed-Integer Optimization model).

The Symmetry Trick: Imagine the square city block. If you rotate it 90 degrees or flip it over, it looks the same. The old search engines wasted time checking the same layout over and over again, just rotated.
- The Fix: The author told the detective, "Assume the first park is on the left wall, the second is on the bottom wall, and so on." By forcing the parks into a specific order on the edges, the detective ignores all the rotated duplicates. It's like telling a librarian to only look at books with red spines, instantly ignoring the blue, green, and yellow ones.
The Result: This "symmetry breaking" made the search 10 times faster. The computer found the best arrangement for 9 parks in 15 minutes on a standard desktop, whereas before it took a whole day.

Step 2: The Final Polish (The "Exact Translation")

The computer gave a "Rough Draft" answer: coordinates like x = 0.712743.... This is a good guess, but in math, we want exact numbers (like $\sqrt{65}$ or fractions), not decimals.

The Detective's Clue: The computer also told us which triangles were the "critical" ones (the smallest ones that are all the same size).
The Algebra Magic: The author took those clues and wrote them as a set of algebraic equations (like a puzzle). Then, they used a "Computer Algebra System" (a math robot that speaks pure logic) to solve the puzzle exactly.
The Outcome: They didn't just get a guess; they got the exact, proven coordinates for the optimal arrangement. For example, for 9 parks, they proved the exact shape involves the square root of 65.

3. The Big Discoveries

By solving this for $n=5$ through $n=9$ , the author found some surprising patterns:

The "Edge Huggers": In the best arrangements, the points love to stick to the walls of the square. For 9 points, at least 5 of them are glued to the edges. This wasn't just a guess; the author proved it mathematically.
The "Cluster Effect": If you look at the sizes of all the triangles (not just the smallest ones), they don't spread out randomly. They clump together into a few specific sizes. It's like if you dropped 100 marbles on a table, and instead of landing everywhere, they only landed on 3 specific shelves. This suggests a hidden, rigid structure in how these points arrange themselves.

4. Why This Matters

Proof, Not Just Guesses: Before this, for $n=9$ , we had a very strong guess that a specific arrangement was best. Now, we have mathematical proof.
Simpler Answers: The author found that the "exact" coordinates for these arrangements are actually much simpler and cleaner than what previous researchers had found.
A New Tool: This "Optimize-Then-Refine" method is a new tool for mathematicians. It combines the brute force of modern computers with the precision of pure math. It can be used for other geometry puzzles, like packing oranges in a box or arranging satellites.

The Bottom Line

Think of this paper as upgrading from a flashlight to a laser pointer.

Before: Researchers were shining a flashlight in a dark room, finding the best spot by trial and error, and hoping it was the absolute best.
Now: The author built a laser pointer that cuts through the darkness, finds the exact spot in minutes, and then uses a microscope to prove why that spot is perfect.

They solved a 70-year-old puzzle for small numbers, proved the answers are exact, and discovered that the universe of these point arrangements is more orderly and "clumpy" than anyone expected.

Here is a detailed technical summary of the paper "From Computational Certification to Exact Coordinates: Heilbronn's Triangle Problem on the Unit Square Using Mixed-Integer Optimization" by Nathan Sudermann-Merx.

1. Problem Definition

The Heilbronn Triangle Problem is a classic problem in discrete geometry. It asks: How should $n$ points be placed within a unit square $[0, 1]^2$ such that the area of the smallest triangle formed by any three of these points is maximized?

Let $\Delta_n$ denote the maximum possible value of this minimal triangle area for a given $n$ .

Asymptotic Context: Heilbronn conjectured $\Delta_n = O(1/n^2)$ , but this was disproven. The current best asymptotic upper bound is $\Delta_n \le n^{-8/7 - 1/2000}$ (Cohen, Pohoata, Zakharov, 2023), while the best lower bound is $\Omega(\log n / n^2)$ .
Small- $n$ Challenge: While asymptotic behavior is studied, determining exact values and configurations for small $n$ (specifically $n \le 16$ ) requires rigorous computational proofs. Prior to this work, proving global optimality for $n=9$ required approximately one day of computation on high-performance clusters.

2. Methodology: The "Optimize-Then-Refine" Framework

The authors propose a two-stage framework that bridges global numerical optimization with exact symbolic computation.

Stage 1: Global Mixed-Integer Nonlinear Programming (MINLP)

The authors formulate the problem as a MINLP to find a numerically certified global optimum.

Baseline Model: The problem is modeled by maximizing a variable $z$ subject to $z \le |A_t|$ for all triangles $t$ , where $A_t$ is the signed area derived from the determinant of vertex coordinates.
Key Enhancements:
1. Symmetry Breaking: The authors exploit the boundary structure of optimal configurations. Based on theoretical proofs (Proposition 3), at least five vertices of the convex hull of the point set must lie on the boundary of the unit square. They fix five points to specific edges (e.g., $x_1=0, y_2=0, x_3=1, y_4=1, x_5=0$ ) and order them counter-clockwise. This eliminates the massive symmetry group ( $D_4 \times S_n$ ) that typically plagues such problems.
2. Sign Fixing: The boundary constraints allow the authors to pre-determine the orientation (sign) of certain triangles, fixing binary variables in the model before solving.
3. Product Substitution: Bilinear terms ( $x_i y_j$ ) are isolated using auxiliary variables to aid the solver's handling of non-convexity.
4. Tighter Bounds: The objective variable $z$ is bounded by the known optimal value of the previous case ( $\Delta_{n-1}$ ).
Solver: The model is solved using Gurobi 13.0 (a commercial MINLP solver) on a standard desktop computer.

Stage 2: Exact Symbolic Refinement

Once a numerical solution is certified:

Structural Identification: The solver output is analyzed to identify "critical triangles" (those with minimal area) and the exact boundary placement of points.
Polynomial System Construction: The condition that critical triangles have equal areas creates a system of polynomial equations.
Symbolic Solution: This system is solved exactly using SymPy (computer algebra).
- For $n=5, 6, 8$ , direct symbolic solving or Gröbner bases are used.
- For $n=9$ , a "numeric-to-symbolic" refinement is employed: the numerical solution is used to identify the underlying algebraic number field (e.g., $\mathbb{Q}(\sqrt{65})$ ), and coordinates are expressed as elements of this field, then verified against the full polynomial system.

3. Key Contributions

Substantial Speedup: The new symmetry-breaking strategy reduces the time to certify global optimality for $n=9$ from ~1 day (previous best) to ~15 minutes on a standard desktop, an improvement of over an order of magnitude.
First Proof for $n=9$ : The paper provides the first rigorous proof that the configuration discovered by Comellas and Yebra (2002) for $n=9$ is globally optimal.
Exact Coordinates: The authors derive closed-form exact coordinates for all optimal configurations with $n = 5, \dots, 9$ . These coordinates are often simpler and more elegant than previous numerical approximations or complex algebraic expressions found in literature.
Reproducibility: All code, input data, and solution files are made publicly available, addressing the issue of "unpublished" best-known configurations in this field.

4. Key Results

The paper confirms and refines the exact values for $\Delta_n$ and provides explicit coordinates:

$n=5$ : $\Delta_5 = \sqrt{3}/9 \approx 0.19245$ .
$n=6$ : $\Delta_6 = 1/8 = 0.125$ . (Notably, there is a one-parameter family of optimal solutions).
$n=7$ : $\Delta_7 \approx 0.083859$ . The exact value is derived from the root of a cubic polynomial ($19f^3 - 27f^2 + 11f - 1 = 0$).
$n=8$ : $\Delta_8 = (\sqrt{13}-1)/36 \approx 0.083859$ .
$n=9$ : $\Delta_9 = \frac{9\sqrt{65} - 11}{320} \approx 0.0747$ . This confirms the optimality of the Comellas-Yebra configuration.

5. Structural Observations & New Research Questions

Analysis of the certified configurations reveals two significant patterns:

Growth of Critical Triangles: The number of triangles achieving the minimal area generally increases with $n$ (e.g., 4 for $n=5$ , 12 for $n=8$ ), though not strictly monotonically. This raises the question of whether a non-trivial lower bound on the number of critical triangles exists as a function of $n$ .
Clustering of Non-Critical Areas: The areas of non-critical triangles do not distribute continuously but cluster around a small number of distinct values. This suggests a hidden structural rigidity in extremal point sets, prompting the question: Do optimal configurations only possess $O(n)$ or even $O(1)$ distinct triangle area values?

6. Significance

Methodological Advance: The paper demonstrates that modern MINLP solvers, when combined with rigorous symmetry breaking and post-processing symbolic refinement, can solve geometric optimization problems that were previously intractable or required massive computational resources.
Theoretical Impact: By providing exact algebraic coordinates, the work moves beyond numerical approximations, allowing for deeper theoretical analysis of the combinatorial geometry of extremal sets.
Foundation for Future Work: The framework is presented as a template for other packing and covering problems in discrete geometry where optimal solutions involve algebraic numbers. The authors suggest that extending this to $n=10$ is feasible with continued hardware and solver improvements.