A method for dense packing discovery

Abstract

The problem of packing a system of particles as densely as possible is foundational in the field of discrete geometry and is a powerful model in the material and biological sciences. As packing problems retreat from the reach of solution by analytic constructions, the importance of an efficient numerical method for conducting \textit{de novo} (from-scratch) searches for dense packings becomes crucial. In this paper, we use the \textit{divide and concur} framework to develop a general search method for the solution of periodic constraint problems, and we apply it to the discovery of dense periodic packings. An important feature of the method is the integration of the unit cell parameters with the other packing variables in the definition of the configuration space. The method we present led to improvements in the densest-known tetrahedron packing which are reported in [arXiv:0910.5226]. Here, we use the method to reproduce the densest known lattice sphere packings and the best known lattice kissing arrangements in up to 14 and 11 dimensions respectively (the first such numerical evidence for their optimality in some of these dimensions). For non-spherical particles, we report a new dense packing of regular four-dimensional simplices with density $\varphi =128/219\approx 0.5845$ and with a similar structure to the densest known tetrahedron packing.

15 pages, 5 figures

References in corpus (11)

• Jammed Hard-Particle Packings: From Kepler to Bernal and Beyond
• Disordered, Quasicrystalline and Crystalline Phases of Densely Packed Tetrahedra
• Dense Packings of the Platonic and Archimedean Solids
• Dense Packings of Polyhedra: Platonic and Archimedean Solids
• Dense crystalline dimer packings of regular tetrahedra
• Divide and concur: A general approach to constraint satisfaction
• Exact Constructions of a Family of Dense Periodic Packings of Tetrahedra
• Dense periodic packings of tetrahedra with small repeating units
• A Dense Packing of Regular Tetrahedra
• Computational Approaches to Lattice Packing and Covering Problems
• Ground states and formal duality relations in the Gaussian core model

Cited by in corpus (8)

• Robust Algorithm to Generate a Diverse Class of Dense Disordered and Ordered Sphere Packings via Linear Programming
• Complexity in surfaces of densest packings for families of polyhedra
• Dense packing crystal structures of physical tetrahedra
• Random perfect lattices and the sphere packing problem
• Upper bound on the packing density of regular tetrahedra and octahedra
• Statistical mechanics of the lattice sphere packing problem
• Novel dense crystalline packings of ellipsoids
• An Efficient Linear Programming Algorithm to Generate the Densest Lattice Sphere Packings