Generation of optimal packings from optimal packings

Thierry Gensane

The electronic journal of combinatorics, Tome 16 (2009) no. 1

Résumé

We define two notions of generation between the various optimal packings ${\cal Q}_m^K$ of $m$ congruent disks in a subset $K$ of ${\Bbb R}^2$. The first one that we call weak generation consists in getting ${\cal Q}_n^K$ by removing $m-n$ disks from ${\cal Q}_m^K$ and by displacing the $n $ remaining congruent disks which grow continuously and do not overlap. During a weak generation of ${\cal Q}_n^K$ from ${\cal Q}_m^K$, we consider the contact graphs ${\cal G}(t)$ of the intermediate packings, they represent the contacts disk-disk and disk-boundary. If for each $t$, the contact graph ${\cal G}(t)$ is isomorphic to the largest common subgraph of the two contact graphs of ${\cal Q}_n^K$ and ${\cal Q}_m^K$, we say that the generation is strong. We call strong generator in $K$, an optimal packing ${\cal Q}_m^K$ which generates strongly all the optimal ${\cal Q}_k^K$ with $k < m$. We conjecture that if $K$ is compact and convex, there exists an infinite sequence of strong generators in $K$. When $K$ is an equilateral triangle, this conjecture seems to be verified by the sequence of hexagonal packings ${\cal Q}_{\Delta (k)}^K$ of $\Delta (k)=k(k+1)/2$ disks. In this domain, we also report that up to $n=34$, the Danzer graph of ${\cal Q}_n^K$ is embedded in the Danzer graph of ${\cal Q}_{\Delta (k)}^K$ with $\Delta (k-1)\leq n < \Delta (k)$. When $K$ is a circle, the first five strong generators appears to be the hexagonal packings defined by Graham and Lubachevsky. When $K$ is a square, we think that our conjecture is verified by a series of packings proposed by Nurmela and al. In the same domain, we give an alternative conjecture by considering another packing pattern.

Détail

DOI : 10.37236/113

Classification : 52C15, 05B40