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.

📐 Le Défi du Triangle Parfait : Comment placer des points pour éviter les "trous" trop petits

Imaginez que vous êtes un architecte chargé de construire une ville sur un terrain carré parfait (un carré d'un mètre de côté). Votre mission est d'y installer n lampadaires (les points).

Mais il y a une règle d'or très stricte : vous devez placer ces lampadaires de manière à ce que le plus petit triangle formé par n'importe quelle combinaison de trois lampadaires soit le plus grand possible.

Pourquoi ? Parce que dans ce monde mathématique, un triangle trop petit, c'est comme un trou dans le sol : c'est dangereux et inefficace. L'objectif est d'éviter les "trous" minuscules. C'est ce qu'on appelle le problème du triangle de Heilbronn.

Ce problème existe depuis des décennies, et pour les petits nombres de lampadaires (de 5 à 9), personne n'était sûr à 100 % de la meilleure façon de les placer. Les mathématiciens avaient de bonnes idées, mais pas de preuve absolue.

🚀 La Solution : Une approche en deux temps (Le "Gros Marteau" et le "Microscope")

L'auteur de ce papier, Nathan, a développé une méthode géniale qu'il appelle "Optimiser, puis Affiner". C'est comme cuisiner un plat complexe : d'abord, on utilise un four puissant pour cuire le plat rapidement, puis on utilise un microscope pour vérifier que chaque ingrédient est exactement au bon endroit.

Étape 1 : Le Four Puissant (L'Optimisation par Ordinateur)

Au lieu de chercher la solution à la main (ce qui prendrait des siècles), Nathan utilise un ordinateur très puissant équipé d'un logiciel spécial (un "solveur").

Le problème : Il y a des millions de façons de placer les points. L'ordinateur risque de tourner en rond, comme un chien qui court après sa queue.
L'astuce géniale : Nathan a inventé une règle pour casser la symétrie. Il dit : "Ok, on va forcer un point à être sur le bord gauche, un autre en bas, un autre en haut..." et on les numérote dans le sens des aiguilles d'une montre.
Le résultat : Cette astuce réduit le nombre de possibilités de millions à quelques milliers. Résultat ? Au lieu de prendre une journée entière de calcul (comme les tentatives précédentes), l'ordinateur trouve la solution optimale pour 9 points en 15 minutes ! C'est une révolution de vitesse.

Étape 2 : Le Microscope (Le Raffinement Exact)

L'ordinateur nous donne une réponse très précise, mais pas parfaite (par exemple : 0,583912...). En mathématiques pures, on veut des nombres exacts, comme des fractions ou des racines carrées (ex: $\sqrt{65}$ ).

Nathan prend les coordonnées approximatives de l'ordinateur.
Il regarde la structure : "Ah, ces deux points sont alignés verticalement ! Ces trois triangles ont exactement la même taille !"
Il transforme ces observations en équations mathématiques pures.
Il utilise un autre logiciel (de "calcul formel") pour résoudre ces équations et obtenir la vraie formule exacte.

🏆 Les Résultats Concrets

Grâce à cette méthode, Nathan a pu :

Prouver définitivement que la meilleure configuration pour 9 points (trouvée par d'autres chercheurs en 2002) est bien la meilleure possible. C'est la première fois que c'est prouvé mathématiquement.
Donner les formules exactes pour les cas de 5 à 9 points. Parfois, ses formules sont même plus simples et plus élégantes que celles trouvées auparavant.
Révéler des secrets cachés : En regardant les solutions, il a remarqué quelque chose d'étrange et de beau : les triangles qui ne sont pas les plus petits (les "non critiques") ne sont pas de tailles aléatoires. Ils se regroupent par "familles" de tailles identiques. C'est comme si la nature aimait l'ordre et la répétition, même dans le chaos apparent.

💡 Pourquoi c'est important ?

Imaginez que vous essayez de ranger des meubles dans un camion. Vous voulez qu'ils tiennent tous sans se toucher. Ce papier nous dit comment le faire de manière mathématiquement parfaite pour de petits nombres de meubles.

Mais plus important encore, il nous montre comment le faire :

En combinant la force brute de l'ordinateur moderne (qui peut tester des milliards de combinaisons).
Avec la rigueur des mathématiques pures (qui donne la preuve absolue).

C'est un pont magnifique entre le monde du "calcul approximatif" et le monde de la "vérité exacte". Et le meilleur ? Tout le code et les résultats sont publics, comme une recette de cuisine partagée avec le monde entier pour que d'autres puissent vérifier et améliorer le travail.

En résumé : Nathan a pris un casse-tête mathématique vieux de 70 ans, a utilisé un ordinateur pour trouver la solution en 15 minutes, puis a utilisé un microscope mathématique pour prouver qu'elle était parfaite, révélant au passage des motifs cachés dans la géométrie de l'univers.

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

Voici un résumé technique détaillé de l'article « From Computational Certification to Exact Coordinates: Heilbronn's Triangle Problem on the Unit Square Using Mixed-Integer Optimization » de Nathan Sudermann-Merx.

1. Le Problème : Le Problème du Triangle de Heilbronn

Le problème de Heilbronn est un problème classique de géométrie discrète qui se pose ainsi : comment placer $n$ points dans un carré unité $[0, 1]^2$ de manière à ce que l'aire du plus petit triangle formé par n'importe quel triplet de ces points soit maximisée ?

On note $\Delta_n$ la valeur optimale de cette aire minimale. Bien que des bornes asymptotiques aient été établies (la conjecture initiale de Heilbronn $\Delta_n = O(1/n^2)$ a été réfutée, et la meilleure borne supérieure actuelle est de l'ordre de $n^{-8/7}$ ), la détermination exacte de $\Delta_n$ et des configurations optimales pour de petites valeurs de $n$ reste un défi computationnel majeur. Jusqu'à présent, les preuves d'optimalité pour $n \ge 7$ nécessitaient des temps de calcul considérables (parfois des jours ou des mois sur des clusters) et ne fournissaient pas toujours de coordonnées exactes symboliques.

2. Méthodologie : Le Cadre « Optimiser puis Raffiner »

L'auteur propose une méthodologie en deux étapes, combinant l'optimisation numérique globale et le calcul symbolique exact :

Étape 1 : Certification Globale par Optimisation Mixte-Entière Non Linéaire (MINLP)

Le problème est formulé comme un problème d'optimisation MINLP.

Modélisation : L'aire d'un triangle est exprimée via le déterminant (formule du « shoelace »). Pour gérer la valeur absolue de l'aire (non lissée), l'auteur introduit des variables binaires pour sélectionner le signe du déterminant, transformant le problème en un modèle non convexe mais gérable par les solveurs modernes.
Stratégies d'amélioration clés :
- Rupture de symétrie basée sur la structure frontière : En s'appuyant sur des preuves théoriques (Lemme 1 et Proposition 3), l'auteur démontre que dans une configuration optimale, au moins 5 sommets de l'enveloppe convexe des points doivent se trouver sur le bord du carré unité. Cette propriété est utilisée pour fixer a priori les coordonnées de 5 points sur les bords et à les ordonner dans le sens antihoraire. Cela élimine la symétrie du groupe diédral $D_4$ (rotations et réflexions du carré) et la symétrie de permutation des points ( $S_n$ ), réduisant drastiquement l'espace de recherche.
- Fixation des signes : Grâce à l'ordonnancement des points sur le bord, les signes des déterminants pour certains triangles sont connus, permettant de fixer des variables binaires sans recherche.
- Substitution de produits : Les termes bilinéaires ( $x_i y_j$ ) sont isolés pour améliorer la relaxation du solveur.
Résultat de l'étape 1 : Le solveur (Gurobi) trouve une solution numérique certifiée avec des bornes inférieure et supérieure égales, prouvant l'optimalité globale de la valeur $\Delta_n$ .

Étape 2 : Raffinement Analytique Exact

Une fois la structure combinatoire identifiée numériquement (quels triangles sont critiques, quels points sont sur le bord, quelles égalités d'aires existent) :

Système polynomial : On impose que les aires des triangles critiques soient égales, ce qui génère un système d'équations polynomiales.
Résolution symbolique : Ce système est résolu exactement à l'aide d'outils d'algèbre computationnelle (SymPy, bases de Gröbner).
Validation : Les solutions symboliques candidates sont vérifiées en les substituant dans le système complet pour éliminer les erreurs d'arrondi numériques.

3. Contributions Principales

Un modèle MINLP renforcé : La stratégie de rupture de symétrie exploitant la structure frontière permet de résoudre le problème pour $n=9$ en 15 minutes sur un ordinateur de bureau standard. Cela représente une amélioration d'un ordre de grandeur par rapport aux travaux précédents (qui prenaient environ un jour avec des solveurs de pointe).
Preuve d'optimalité et coordonnées exactes : L'article fournit la première preuve formelle que la configuration découverte par Comellas et Yebra en 2002 pour $n=9$ est globalement optimale. De plus, il dérive les coordonnées exactes symboliques (sous forme de racines de polynômes) pour toutes les configurations optimales de $n=5$ à $n=9$ .
Comparaison avec l'état de l'art : Contrairement à des approches récentes (Monji et al., 2025) qui utilisent des heuristiques, des pré-traitements lourds et des conjectures structurelles non prouvées, la méthode proposée repose entièrement sur des preuves mathématiques rigoureuses pour ses contraintes de modélisation, sans nécessiter de pré-calculs d'optimisation.
Reproductibilité : Tous les codes sources, les données d'entrée et les fichiers de solution sont rendus publics.

4. Résultats Clés

L'auteur a résolu le problème pour $n \in \{5, \dots, 9\}$ avec des résultats suivants :

$n=5$ : $\Delta_5 = \sqrt{3}/9 \approx 0.19245$ .
$n=6$ : $\Delta_6 = 1/8 = 0.125$ . Une famille à un paramètre de solutions optimales est identifiée.
$n=7$ : $\Delta_7 \approx 0.08386$ . Les coordonnées exactes sont exprimées en fonction d'une racine d'un polynôme cubique irréductible ($19f^3 - 27f^2 + 11f - 1 = 0$).
$n=8$ : $\Delta_8 = (\sqrt{13}-1)/36$ . La solution est unique et possède une symétrie centrale.
$n=9$ : $\Delta_9 = (-11 + 9\sqrt{65})/320$ . C'est la première preuve d'optimalité globale pour ce cas, confirmant la configuration de Comellas et Yebra.

5. Observations Structurelles et Questions de Recherche

L'analyse des configurations certifiées révèle deux phénomènes intéressants :

Croissance du nombre de triangles critiques : Le nombre de triangles ayant l'aire minimale croît avec $n$ (de 4 pour $n=5$ à 11 pour $n=9$ ), bien que la croissance ne soit pas strictement monotone.
Regroupement (Clustering) des aires non critiques : Les aires des triangles qui ne sont pas critiques ne sont pas distribuées de manière continue, mais se regroupent autour d'un petit nombre de valeurs distinctes. Cela suggère une rigidité structurelle cachée dans les configurations extrêmes.

6. Signification et Perspectives

Cet article démontre la maturité des solveurs d'optimisation mixte-entière non linéaire modernes (MINLP) pour résoudre des problèmes géométriques complexes qui étaient auparavant hors de portée. La combinaison de la certification numérique et du raffinement symbolique offre une nouvelle voie pour résoudre des problèmes de géométrie discrète où les solutions optimales impliquent des nombres algébriques.

Les auteurs suggèrent que cette approche pourrait être étendue à $n=10$ avec les progrès futurs du matériel et des solveurs, et que l'étude du regroupement des aires des triangles pourrait mener à de nouvelles théories en géométrie combinatoire des ensembles de points extrémaux.