Repeated Patterns of Dense Packings of Equal Disks in a Square

  • R. L. Graham
  • B. D. Lubachevsky


We examine sequences of dense packings of $n$ congruent non-overlapping disks inside a square which follow specific patterns as $n$ increases along certain values, $n = n(1), n(2),... n(k),...$. Extending and improving previous work of Nurmela and Östergård where previous patterns for $n = n(k)$ of the form $ k^2$, $ k^2-1$, $k^2-3$, $k(k+1)$, and $4k^2+k$ were observed, we identify new patterns for $n = k^2-2$ and $n = k^2+ \lfloor k/2 \rfloor$. We also find denser packings than those in Nurmela and Östergård for $n =$21, 28, 34, 40, 43, 44, 45, and 47. In addition, we produce what we conjecture to be optimal packings for $n =$51, 52, 54, 55, 56, 60, and 61. Finally, for each identified sequence $n(1), n(2),... n(k),...$ which corresponds to some specific repeated pattern, we identify a threshold index $k_0$, for which the packing appears to be optimal for $k \le k_0$, but for which the packing is not optimal (or does not exist) for $k > k_0$.

Article Number