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

Each language version is independently generated for its own context, not a direct translation.

De Heilbronn-Driehoek: Hoe je de kleinste driehoek zo groot mogelijk maakt

Stel je voor dat je een vierkant stuk land hebt (een eenheidsvierkant) en je moet er n punten op zetten. Je doel is heel slim: je wilt de punten zo plaatsen dat de kleinste driehoek die je kunt vormen door drie willekeurige punten te verbinden, zo groot mogelijk is.

Klinkt simpel? Het is een van die wiskundige puzzels die al decennialang hersenspinsels heeft opgeleverd. Dit heet het Heilbronn-driehoekprobleem.

Deze paper vertelt het verhaal van hoe een nieuwe, slimme manier om dit probleem op te lossen, de rekentijd van een dag terugbrengt tot slechts 15 minuten, en bovendien exacte antwoorden geeft in plaats van benaderingen.

Hier is de uitleg, vertaald naar alledaags taalgebruik:

1. Het Probleem: De "Kleine Driehoek"

Stel je een vierkante kamer voor. Je gooit er een paar ballen in. Als je drie ballen met een touwtje verbindt, krijg je een driehoek.

Als je de ballen te dicht bij elkaar gooit, krijg je een heel klein driehoekje.
Als je ze te ver uit elkaar gooit, krijg je misschien grote driehoeken, maar dan zijn er misschien weer andere drie ballen die heel dicht bij elkaar liggen en een klein driehoekje vormen.

De vraag is: Hoe gooi je de ballen precies zodat het kleinste driehoekje dat er ontstaat, zo groot mogelijk is?

Voor een klein aantal ballen (bijvoorbeeld 5 of 6) weten we het antwoord al. Maar voor 9 ballen was het een enorme uitdaging.

2. De Oude Manier: "Gissen en Gokken"

Vroeger deden wiskundigen dit door te simuleren. Ze lieten computers duizenden keren willekeurig ballen gooien, keken welke configuratie het beste was, en probeerden die dan een beetje te verbeteren.

Het nadeel: Je weet nooit zeker of je het beste antwoord hebt gevonden. Misschien is er ergens een nog betere plek waar je de computer niet naar gekeken heeft.
Voor 9 punten duurde het zelfs een hele dag op krachtige computers om een goed antwoord te vinden, en zelfs dan was het niet 100% zeker dat het de allerbeste was.

3. De Nieuwe Manier: "De Slimme Bouwmeester"

De auteurs van deze paper hebben een nieuwe aanpak bedacht: "Eerst optimaliseren, dan verfijnen". Ze gebruiken twee gereedschappen die samenwerken als een perfecte bouwploeg.

Stap 1: De Wiskundige "Bouwschema" (Mixed-Integer Optimization)

Stel je voor dat je een bouwschema maakt voor een huis. In plaats van te gokken waar de muren komen, geef je de computer strikte regels:

"Er moet minstens één muur aan de linkerkant staan."
"De hoekpunten moeten in een bepaalde volgorde liggen."
"Deze hoekpunten mogen niet op dezelfde plek zitten."

Dit is wat de auteurs doen met symmetrie-breking. In plaats van dat de computer alle mogelijke rotaties en spiegelingen van het vierkant moet checken (wat miljoenen keer hetzelfde is), zeggen ze: "Oké, we doen het zo: punt 1 zit links, punt 2 onder, punt 3 rechts...".
Dit reduceert de zoekruimte enorm. Het is alsof je in plaats van een heel bos te doorzoeken, alleen de paden bekijkt die naar de schat leiden.

Het resultaat: De computer vindt in 15 minuten (in plaats van een dag) een antwoord dat wiskundig bewezen is het beste mogelijke antwoord.

Stap 2: De "Exacte Vertaler" (Exact Symbolic Computation)

De computer in Stap 1 geeft een antwoord met cijfers zoals 0.135249.... Dat is goed, maar wiskundigen willen de exacte formule (bijvoorbeeld met wortels en breuken).
Stel je voor dat de computer een schets heeft getekend. De tweede stap is een "vertaler" die die schets omzet in een perfect, exact architecturaal plan.

De computer kijkt naar de schets en zegt: "Ah, deze lijnen lijken op elkaar, en deze hoek is precies 45 graden."
De "vertaler" (een computerprogramma voor algebra) lost dan de exacte vergelijkingen op.

Zo krijgen we niet alleen een getal, maar een exacte formule voor de positie van elke punt.

4. Wat hebben ze ontdekt?

Met deze nieuwe methode hebben ze voor het eerst bewezen dat de beste manier om 9 punten te plaatsen, precies die is die in 2002 al door anderen was gevonden (maar niet bewezen). Ze hebben ook de exacte coördinaten voor 5 tot en met 9 punten gevonden.

Bovendien zagen ze iets vreemds en moois:

De "Kritieke" Driehoeken: Er zijn een paar driehoeken die precies even groot zijn (de kleinste).
De "Niet-Kritieke" Driehoeken: Alle andere driehoeken zijn groter, maar ze lijken te "klonteren". Ze vallen niet willekeurig uit, maar groeperen zich rond een paar specifieke waarden.
- Analogie: Stel je voor dat je een bak met ballen schudt. Je zou verwachten dat ze overal liggen. Maar hier lijken ze zich netjes in rijen te zetten. Dit suggereert dat er dieper in de wiskunde nog onontdekte patronen en symmetrieën schuilen.

5. Waarom is dit belangrijk?

Snelheid: Wat vroeger dagen duurde, duurt nu minuten.
Betrouwbaarheid: We hebben nu 100% zekerheid dat het antwoord het beste is.
Nieuwe vragen: De ontdekking dat de driehoeksgroottes "klonteren" roept nieuwe vragen op. Waarom gedragen deze punten zich zo? Dit kan helpen bij het oplossen van andere problemen in de meetkunde.

Kortom: De auteurs hebben een slimme combinatie van een "slimme bouwer" (die de zoekruimte verkleint) en een "perfecte vertaler" (die exacte formules maakt) gebruikt om een oude wiskundige puzzel op te lossen die al decennialang een raadsel was. Ze hebben niet alleen het antwoord gevonden, maar ook bewezen dat het het enige juiste antwoord is.

Each language version is independently generated for its own context, not a direct translation.

Hier is een gedetailleerde technische samenvatting van het artikel "From Computational Certification to Exact Coordinates: Heilbronn's Triangle Problem on the Unit Square Using Mixed-Integer Optimization" in het Nederlands.

Titel en Context

Titel: Van computationele certificering naar exacte coördinaten: Heilbronn's Driehoekprobleem op de eenheidsvierkant met behulp van gemengd-integer optimalisatie.
Auteur: Nathan Sudermann-Merx (Instituut voor Informatica, DHBW Mannheim).
Datum: 13 maart 2026.

1. Het Probleem: Heilbronn's Driehoekprobleem

Het Heilbronn-driehoekprobleem is een klassiek vraagstuk uit de discrete meetkunde. De vraag luidt:

Hoe moeten $n$ punten in een eenheidsvierkant $[0,1]^2$ worden geplaatst zodat de oppervlakte van de kleinste driehoek die door drie willekeurige punten wordt gevormd, zo groot mogelijk is?

De optimale waarde wordt aangeduid als $\Delta_n$ . Hoewel er asymptotische schattingen zijn (bijvoorbeeld de recente bovengrens van Cohen, Pohoata en Zakharov), zijn exacte oplossingen voor kleine waarden van $n$ moeilijk te vinden en te bewijzen. Voor $n=9$ was de vorige beste berekening ongeveer een dag nodig op een cluster, zonder dat de exacte algebraïsche coördinaten formeel waren bewezen als globaal optimaal.

2. Methodologie: Een "Optimize-then-Refine" Kader

De auteur introduceert een tweestapskader dat numerieke optimalisatie combineert met exacte symbolische berekening:

Stap 1: Globale Numerieke Certificering (Mixed-Integer Nonlinear Programming - MINLP)

Het probleem wordt geformuleerd als een MINLP-model. De kernuitdaging is de niet-gladde objectief functie (maximaliseren van het minimum van absolute waarden).

Basisformulering: Gebruik van een binaire variabele $b_t$ per driehoek $t$ om het teken van de georiënteerde oppervlakte te selecteren, waardoor de absolute waarde wordt gemodelleerd zonder grote $M$ -parameters (big-M).
Symmetriebreking (Cruciaal): Het model heeft enorme symmetrie (rotaties, spiegelingen van het vierkant en permutaties van puntlabels). De auteur ontwikkelt een nieuwe strategie gebaseerd op de randstructuur van optimale configuraties:
- Bewezen dat ten minste vijf hoekpunten van de convexe hull op de rand van het vierkant liggen.
- Vijf punten worden vastgezet op specifieke randen (links, onder, rechts, boven) in een tegen de klok in volgorde.
- De overige punten worden gesorteerd op hun $x$ -coördinaat.
- Dit elimineert de symmetriegroep volledig en fixeert een aantal continue variabelen en binaire variabelen vooraf.
Resultaat: Dit leidt tot een veel sterker model dat in 15 minuten op een standaard desktopcomputer de globale optimaliteit voor $n=9$ kan certificeren (een verbetering met meer dan een orde van grootte ten opzichte van eerdere werken).

Stap 2: Exacte Symbolische Verfijning

Zodra de numerieke oplossing en de structuur (welke driehoeken kritiek zijn, welke punten op de rand liggen) bekend zijn:

De numerieke waarden worden gebruikt om een ansatz (parametrisch model) op te stellen.
De voorwaarde dat de oppervlakten van de kritieke driehoeken gelijk moeten zijn, leidt tot een stelsel van polynoomvergelijkingen.
Dit stelsel wordt exact opgelost met computeralgebra-systemen (SymPy):
- Voor kleine $n$ (5, 6, 8) via directe symbolische oplossing.
- Voor $n=7$ via Gröbner-basisberekening.
- Voor $n=9$ via een "numeriek-naar-symbolisch" verfijning, waarbij het onderliggende getallenlichaam (bijv. $\mathbb{Q}(\sqrt{65})$ ) wordt geïdentificeerd en alle coördinaten exact worden afgeleid.
Elke kandidaat-oplossing wordt symbolisch geverifieerd om numerieke fouten uit te sluiten.

3. Belangrijkste Bijdragen

Sterkere MINLP-formulering: Een nieuw model met geavanceerde symmetriebreking dat de rekentijd voor $n=9$ van ~1 dag reduceert tot ~15 minuten.
Eerste formeel bewezen optimaliteit voor $n=9$ : Het bewijst dat de configuratie gevonden door Comellas en Yebra (2002) globaal optimaal is.
Exacte Coördinaten: Het levert de eerste gesloten-vorm exacte algebraïsche coördinaten voor alle optimale configuraties met $n=5$ tot en met $n=9$ .
Reproduceerbaarheid: Alle code, data en oplossingen zijn openbaar beschikbaar gesteld.

4. Resultaten voor $n=5$ t/m $n=9$

De studie bevestigt eerdere beste resultaten en vereenvoudigt vaak de presentatie van de coördinaten:

$n=5$ : $\Delta_5 = \sqrt{3}/9$ . Exacte coördinaten gevonden.
$n=6$ : $\Delta_6 = 1/8$ . Er bestaat een één-parameter familie van optimale oplossingen.
$n=7$ : $\Delta_7 \approx 0.083859$ . De coördinaten worden uitgedrukt via de wortel van een irreducibele kubische vergelijking ($19f^3 - 27f^2 + 11f - 1 = 0$). Dit is algebraïsch eenvoudiger dan eerdere rapporten.
$n=8$ : $\Delta_8 = (\sqrt{13}-1)/36$ . Unieke oplossing met punt-symmetrie.
$n=9$ : $\Delta_9 = (-11 + 9\sqrt{65})/320$ . Unieke oplossing met spiegelsymmetrie over de anti-diagonaal.

5. Structurele Observaties en Nieuwe Vragen

Uit de analyse van de gecertificeerde configuraties komen twee opvallende patronen naar voren:

Aantal kritieke driehoeken: Het aantal driehoeken met de minimale oppervlakte groeit met $n$ (van 4 bij $n=5$ tot 12 bij $n=8$ , met een dip naar 11 bij $n=9$ ). Dit roept de vraag op of er een niet-triviale ondergrens is voor dit aantal als functie van $n$ .
Clustering van niet-kritieke oppervlakten: De oppervlakten van de niet-kritieke driehoeken (die groter zijn dan het minimum) clusteren rond een klein aantal discrete waarden in plaats van willekeurig te spreiden. Dit suggereert een diepere structurele rigiditeit in de extremale puntverzamelingen.

6. Significatie

Dit werk toont aan dat moderne MINLP-oplossers (zoals Gurobi), wanneer ze worden gecombineerd met slimme symmetriebreking en exacte algebra, krachtige instrumenten zijn voor het oplossen van complexe meetkundige optimalisatieproblemen die voorheen onbereikbaar waren. Het "Optimize-then-Refine"-kader biedt een blauwdruk voor het bewijzen van optimaliteit en het afleiden van exacte wiskundige structuren in andere verpakkings- en dekkingsproblemen binnen de discrete meetkunde.