Lava, donuts and printing

We have just returned from vacation touring the British isles. In particular, we visited the Giant's causeway in Belfast, Northern Ireland. The area is covered by more than 40,000 basalt columns with many of them having a shape close to a hexagonal column (similar to the shape of a pencil). They were formed when lava were cooling and shrinking. Why the hexagonal shapes? This might be due to the fact that a hexagonal lattice arrangement of circles on a plane is the densest arrangement of circles of the same size [1]. The hexagonal lattice arrangement is also the covering of circular disk with the least overlap. Many arrangements of objects in nature such as honeycombs have this hexagonal arrangement. The Voronoi regions of this arrangment are hexagons. Since this arrangement is periodic in two (non perpenticular) axes, one can view this as a periodic packing on the torus, provided the density matches the dimension of the torus. When the density does not match, we don't have a hexagonal packing on the torus, and it is not clear what the densest packing is. This has applications in digital halftoning [2]. The only difference in the halftoning application is that the circle centers are points on a discrete grid on the torus.  We studied 2 algorithms to generate such packing on the torus. The first algorithm is the Direct Binary Search (DBS) algorithm [3] and generate patterns like this:

The second algorithm is based on the Riesz energy minimization theory of Hardin and Saff [4] and we were able to obtain patterns that are more uniform than DBS:

In both cases, they look like the patterns found on Giant's causeway:

In 3 dimensions, the densest packing is the face-centered cubic (FCC) lattice packing (also known as the "canonball" packing).  It was conjectured to be the densest packing by Kepler in 1611, and it was only proved relatively recently by Hales with a proof first announced in 1998 and the correctness of the lengthy proof checked by computer in 2014.

References:
[1] J. Conway and N. J. A. Sloane, "Sphere Packings, Lattices and Groups", Springer, 3rd Edition, 1998.
[2] C. W. Wu, B. Trager, K. Chandu and M. Stanich, "A Riesz energy based approach to generating dispersed dot patterns for halftoning applications," Proceedings of SPIE-IS&T Electronic Imaging, SPIE, vol. 9015, pp. 90150Q, 2014,
[3]  J. P. Allebach, “DBS: retrospective and future directions,” in Proceedings of SPIE, 4300, pp. 358–376, 2001.
[4] D. P. Hardin and E. B. Saff, “Discretizing manifolds via minimum energy points,” Notices of the AMS 51(10), pp. 1186–1194, 2004.