Densest plane group packings of regular polygons

Packings of regular convex polygons ($n$-gons) that are sufficiently dense have been studied extensively in the context of modeling physical and biological systems as well as discrete and computational geometry. Former results were mainly regarding densest lattice or double-lattice configurations. Here we consider all two-dimensional crystallographic symmetry groups (plane groups) by restricting the configuration space of the general packing problem of congruent copies of a compact subset of the two-dimensional Euclidean space to particular isomorphism classes of the discrete group of isometries. We formulate the plane group packing problem as a nonlinear constrained optimization problem. By means of the Entropic Trust Region Packing Algorithm that approximately solves this problem, we examine some known and unknown densest packings of various $n$-gons in all 17 plane groups and state conjectures about common symmetries of the densest plane group packings for every $n$-gon.

Figure 1

The colored rank table of plane groups in relation to the number of vertices $n$ of an $n$-gon. For every $n=3,...,35$ plane groups are ordered according to densities in Table 1, and a color is assigned based on rank $r$ ranging from one to $r_{max}$. The value of $r_{max}$ depends on a specific $n$-gon.

Figure 2

Densest configurations of (from top to bottom) pentagon, heptagon, enneagon, and dodecagon in plane groups $p2$, $p2gg$, $pg$, $p3$, and $p1$ with the following densities: pentagon in $p2/p2gg/pg\approxeq 0.92131$, $p3\approxeq 0.87048,$ and $p1\approxeq 0.81725$; heptagon in $p2/p2gg/pg\approxeq 0.89269$, $p3\approxeq 0.88085,$ and $p1\approxeq 0.86019$; enneagon in $p2\approxeq 0.90103$, $p2gg\approxeq 0.89989$, $pg\approxeq 0.89860,$ and $p3/p1\approxeq 0.88773$; dodecagon in $p2/p2gg/pg/p3/p1\approxeq 0.92820$. The blue parallelogram denotes the primitive cell of the respective configuration. Colors represent symmetry operations modulo lattice translations.

Figure 3

Densities of the densest packings of examined $n$-gons in the $p2/p2gg/pg/p3/p1$ plane groups class. The red line denotes the density of the densest disk packing in this plane group class.

Figure 4

Densest configurations of (top) heptagon, (middle) endecagon, and (bottom) dodecagon in plane groups $p2mg$, $cm$, and $p4$ with the following densities: heptagon in $p2mg/cm\approxeq 0.84226$ and $p4\approxeq 0.84219$; endecagon in $p2mg\approxeq 0.83116$, $cm\approxeq 0.82795,$ and $p4\approxeq 0.83780$; dodecagon in $p2mg/cm/p4\approxeq 0.86156$. The blue parallelogram denotes the primitive cell of the respective configuration. Colors represent symmetry operations modulo lattice translations.

Figure 5

Two nonisomorphic densest $p2mg$ packings of a decagon obtained by ETRPA with packing density of approximately 0.83722.

Figure 6

Densities of the densest packings of examined $n$-gons in the $p2mg/cm/p4$ plane groups class. The red line denotes the density of the in this plane group class.

Figure 7

Densest configurations of (top) pentagon, (middle) octagon, and (bottom) decagon in plane groups $p4gm$, $c2mm$, $p2mm,$ and $pm$ with the following densities: pentagon in $p4gm\approxeq 0.71119$, $c2mm\approxeq 0.71714,$ and $p2mm/pm\approxeq 0.69098$; octagon in $p4gm/c2mm/p2mm/pm\approxeq 0.82842$; decagon in $p4gm\approxeq 0.77205$ and $c2mm/p2mm/pm\approxeq 0.77254$. The blue parallelogram denotes the primitive cell of the respective configuration. Colors represent symmetry operations modulo lattice translations.

Figure 8

Manually constructed $pm$ packings of a (left) pentagon and (right) decagon from their respective densest $p2mm$ packing configurations with approximately equal density as their $p2mm$ counterparts presented in Fig. 7.

Figure 9

Densities of the densest packings of examined $n$-gons in the $p4gm/c2mm/p2mm/pm$ plane groups class. The red line denotes the density of the densest disk packing in this plane group class.

Figure 10

Densest configurations of (from top to bottom) hexagon, octagon, and dodecagon in plane groups $p6$, $p31m$, $p3m1$, $p4mm$, and $p6mm$ with the following densities: hexagon in $p6\approxeq 0.85714$, $p31m\approxeq 0.71999$, $p3m1\approxeq 0.66666$, $p4mm\approxeq 0.52148,$ and $p6mm\approxeq 0.47999$; octagon in $p6\approxeq 0.76438$, $p31m\approxeq 0.71565$, $p3m1\approxeq 0.57980$, $p4mm\approxeq 0.56854,$ and $p6mm\approxeq 0.48235$; dodecagon in $p6\approxeq 0.79560$, $p31m\approxeq 0.74613$, $p3m1\approxeq 0.61880$, $p4mm\approxeq 0.53589,$ and $p6mm\approxeq 0.49742$. The blue parallelogram denotes the primitive cell of the respective configuration. Colors represent symmetry operations modulo lattice translations.

Figure 11

Densities of the densest packings of examined $n$-gons in the $p6/p31m/p3m1/p4mm/p6mm$ plane groups class. The colored lines denote the density of the corresponding densest plane group disk packings.

Figure 12

$p3/p1$ packing of the enneagon with a packing density of approximately 0.87358, manually constructed from the enneagon's densest $p2$ packing configuration in Fig. 2.