Empilement de cercles dans un triangle isocèle rectangle

L'empilement de cercles dans un triangle isocèle rectangle est un problème d'empilement bidimensionnel dont l'objectif est d'empiler des cercles unités identiques de nombre $n$ dans le triangle isocèle rectangle le plus petit possible.

Les solutions minimales sont indiquées dans le tableau ci-dessous[1].

Des solutions optimales sont connues pour n < 8[2].

En 2011, un algorithme heuristique a trouvé 18 améliorations sur les optimum connus précédemment, le plus petit étant pour n < 13[3].

Nombre de cercle $n$	Longueur d'un côté du triangle autre que l’hypoténuse	Figure
1	$2+{\sqrt {2}}\approx 3,414...$
2	$2{\sqrt {2}}\approx 4,828...$
3	$4+{\sqrt {2}}\approx 5,414...$
4	$2+3{\sqrt {2}}\approx 6,242...$
5	$4+{\sqrt {2}}+{\sqrt {3}}\approx 7,146...$
6	$6+{\sqrt {2}}\approx 7,414...$
7	$4+{\sqrt {2}}+{\sqrt {2+4{\sqrt {2}}}}\approx 8,181...$
8	$2+3{\sqrt {2}}+{\sqrt {6}}\approx 8,692...$
9	$2+5{\sqrt {2}}\approx 9,071...$
10	$8+{\sqrt {2}}\approx 9,414...$
11	$5+3{\sqrt {2}}+{\dfrac {\sqrt {6}}{3}}\approx 10,059...$
12	10,422...
13	10,798...
14	$2+3{\sqrt {2}}+2{\sqrt {6}}\approx 11,141...$
15	$10+{\sqrt {2}}\approx 11,414...$

Références

Eckard Specht, « The best known packings of equal circles in an isosceles right triangle », 11 mars 2011 (consulté le 1^er mai 2011)
Y. Xu, « On the minimum distance determined by n (≤ 7) points in an isoscele right triangle », Acta Mathematicae Applicatae Sinica, vol. 12, n^o 2,‎ 1996, p. 169–175 (DOI 10.1007/BF02007736)
C. O. López et J. E. Beasley, « A heuristic for the circle packing problem with a variety of containers », European Journal of Operational Research, vol. 214, n^o 3,‎ 2011, p. 512 (DOI 10.1016/j.ejor.2011.04.024)

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.