empilement de polyèdres

Imaginez une boîte que l'on remplit avec des cubes ou des tétraèdres. On peut déplacer et orienter chaque solide, mais leurs intérieurs ne doivent jamais se chevaucher. Leurs faces, leurs arêtes ou leurs sommets peuvent en revanche se toucher.

L'enjeu est de laisser le moins de vide possible. La densité compare le volume occupé par les polyèdres au volume total considéré. La forme des faces et la manière dont les sommets se rencontrent peuvent rendre une disposition serrée très différente d'un simple rangement en rangées.

Un empilement de polyèdres est une famille de copies d'un ou de plusieurs solides polyédriques placées dans l'espace. Les intérieurs de deux copies sont disjoints ; leurs frontières peuvent être disjointes ou tangentes. Les translations et les orientations font partie des choix de la disposition.

Dans un empilement périodique, on choisit une cellule qui se répète. Le volume occupé dans cette cellule est noté V_occupé, et le volume de la cellule V_cellule. La densité volumique, notée par la lettre grecque phi, vaut $\phi =V_{\mathrm{o}\mathrm{c}\mathrm{c}\mathrm{u}\mathrm{p}\acute{\mathrm{e}}}\mathrm{/}{V}_{\mathrm{c}\mathrm{e}\mathrm{l}\mathrm{l}\mathrm{u}\mathrm{l}\mathrm{e}}\backslash varphi=V\_\{\backslash mathrm\{occupé\}\}/V\_\{\backslash mathrm\{cellule\}\}$. Elle est comprise entre 0 et 1 : plus elle est proche de 1, moins la cellule contient de vide. Pour une disposition non périodique, il faut préciser le processus de limite utilisé quand la région observée grandit.

Le problème d'optimisation cherche la plus grande densité parmi les dispositions admissibles. Il dépend du polyèdre choisi : les solides de Platon et les solides d'Archimède n'imposent pas les mêmes contacts. L'étude des sphères constitue le problème analogue, mais ne donne pas automatiquement la réponse pour des solides à faces planes. Les travaux de Salvatore Torquato et Yang Jiao ont exploré systématiquement ces familles par optimisation ; le tétraèdre montre notamment que les arrangements les plus évidents ne sont pas nécessairement les plus denses.

Considérons un empilement périodique de cubes unité. La cellule fondamentale est elle-même un cube de côté 1, occupé par un cube identique. Les cellules voisines partagent leurs faces, tandis que les intérieurs des cubes restent disjoints.

Données.
Solide : un cube de côté 1.
Cellule : un cube de côté 1.
Nombre de cubes par cellule : 1.
Contacts autorisés : face contre face.

1. Le volume du cube placé dans la cellule vaut 1 × 1 × 1 = 1.

2. Le volume de la cellule vaut lui aussi 1 × 1 × 1 = 1.

3. Le volume occupé est 1, puisqu'une seule copie du cube remplit la cellule sans chevauchement.

4. La densité est donc $\phi =1\mathrm{/}1=1\backslash varphi=1/1=1$. La cellule ne contient aucun vide ; aucune densité ne peut dépasser 1.

Le contrôle se refait sur un bloc de 2 × 2 × 2 cellules : il contient 8 cubes de volume 1 dans un volume total de 8. Le quotient 8/8 redonne exactement 1.

Pour comparer deux rangements d'un même polyèdre, on fixe une cellule de référence, on additionne le volume qui y est occupé et on divise par le volume de la cellule. Le rangement de densité supérieure est le meilleur des deux candidats, sans que cette comparaison prouve qu'il est optimal parmi tous les rangements possibles.

Dans une simulation, on modifie les positions et les orientations, puis on rejette toute configuration où deux intérieurs se chevauchent. Une recherche par optimisation est préférable à un rangement manuel lorsque de nombreuses configurations doivent être comparées.

Pour modéliser des objets réels, le modèle polyédrique convient lorsque les faces planes, les arêtes et les sommets gouvernent les contacts. Si les objets sont assimilables à des sphères, il faut employer le problème d'empilement de sphères plutôt que leur attribuer artificiellement des faces.

Empilement de sphères. La frontière de chaque objet est courbe, tandis qu'un polyèdre possède des faces planes, des arêtes et des sommets. Un lot de boules idéalisées relève du premier problème ; un lot de cubes idéalisés relève du second.

Pavage de l'espace. Un pavage remplit tout l'espace sans trou ni chevauchement, donc sa densité vaut 1. Un empilement autorise des vides et cherche à les réduire. L'empilement de cubes de l'exemple est aussi un pavage ; un empilement comportant des interstices ne l'est pas.

Recouvrement. Dans un recouvrement, les solides peuvent se chevaucher afin que chaque point de l'espace appartienne à au moins une copie. Dans un empilement, un chevauchement des intérieurs rend au contraire la configuration inadmissible.

Boîte finie. Près de la paroi, des vides peuvent apparaître seulement à cause du bord. Une densité mesurée dans une petite boîte ne représente donc pas automatiquement celle d'un empilement infini. Il faut annoncer le contenant ou utiliser une cellule périodique.

Contact ou chevauchement. Deux polyèdres peuvent partager une partie de leur frontière sans enfreindre la règle. En revanche, dès qu'une région de volume positif appartient à leurs deux intérieurs, la disposition n'est plus un empilement admissible.

Densité locale et optimum global. Une modification peut resserrer quelques solides tout en créant davantage de vide ailleurs. Il faut recalculer le quotient sur la cellule entière. De même, le meilleur candidat trouvé par un algorithme ne devient un maximum démontré que si une preuve exclut toute configuration plus dense.

Cas charnière. La densité 1 signifie que le volume considéré est entièrement rempli ; elle ne signifie pas que tous les polyèdres peuvent atteindre cette valeur. Pour une forme donnée, il faut construire un pavage ou déterminer une borne propre à cette forme.

La fiche densité d'empilement précise la grandeur optimisée et la manière de comparer deux dispositions.

La fiche polyèdre revient sur les faces, les arêtes et les sommets qui gouvernent les contacts.

La fiche solide de Platon situe la famille régulière étudiée dans les recherches citées.

La fiche tétraèdre détaille le solide dont les empilements denses déjouent les configurations naïves.