D488. Les triangulations de Maximin Imprimer
D4. Pavage du plan et de l'espace - Dissection

calculator_edit.png  

Pour les valeurs entières de k respectivement égales à 6,5,8 et 7(*)  pourriez-vous aider Maximin à placer k points à l’intérieur d’un carré unité (côtés inclus) de sorte que l’aire A(k) du plus petit triangle formé par trois de ces points soit maximale ? Quelle est la valeur correspondante de A(k) ?
(*) Nota : les valeurs sont données par ordre de difficulté croissante des triangulations.

 

 Solution



Ce problème est connu sous le nom du triangle d'Heilbronn qui a fait l'objet de multiples études depuis que Hans Heilbronn l'a posé au milieu du siècle dernier.
Pour les différentes valeurs de k de l'énoncépdfBernard Vignes,pdfJean Nicot,pdfPaul Voyer et pdfPatrick Gordon ont proposé de multiples triangulations avec des points formant le plus souvent des polygones réguliers ou des polygones non réguliers admettant des axes de symétrie parallèles aux côtés du carré. Pour k = 5 et k = 6, les résultats optimaux ont été obtenus. Pour k = 7 et k = 8, les choses se compliquent et il faut concevoir un placement des points qui admettent seulement un centre de symètrie.
Deux lecteurs ont repéré sur Internet l'article pdfNew lower bounds for Heilbronn numbers de Francesc Comellas et J. Luis A. Yebra qui décrivent les résultats optimaux obtenus à ce jour pour tout k ? 12.