Salvatore Torquato ^a)
Princeton Materials Institute, and Department of Chemistry, Princeton University, Princeton, New Jersey 08544

Frank H. Stillinger
Department of Chemistry, Princeton University, Princeton, New Jersey 08544

Robert Connelly
Department of Mathematics, Cornell University, Ithaca, New York 14853

Received 3 September 2003; received in revised form 25 November 2003; accepted 26 November 2003. Available online 17 January 2004. J. Comput. Phys. 197, 139-166 (2004).

Abstract

   Jamming in hard-particle packings has been the subject of considerable interest in recent years. In a paper by Torquato and Stillinger [J. Phys. Chem. B 105 (2001)], a classification scheme of jammed packings into hierarchical categories of locally, collectively and strictly jammed configurations has been proposed. They suggest that these jamming categories can be tested using numerical algorithms that analyze an equivalent contact network of the packing under applied displacements, but leave the design of such algorithms as a future task. In this work, we present a rigorous and practical algorithm to assess whether an ideal hard-sphere packing in two or three dimensions is jammed according to the aforementioned categories. The algorithm is based on linear programming and is applicable to regular as well as random packings of finite size with hard-wall and periodic boundary conditions. If the packing is not jammed, the algorithm yields representative multi-particle unjamming motions. Furthermore, we extend the jamming categories and the testing algorithm to packings with significant interparticle gaps. We describe in detail two variants of the proposed randomized linear programming approach to test for jamming in hard-sphere packings. The first algorithm treats ideal packings in which particles form perfect contacts. Another algorithm treats the case of jamming in packings with significant interparticle gaps. This extended algorithm allows one to explore more fully the nature of the feasible particle displacements. We have implemented the algorithms and applied them to ordered as well as random packings of circular disks and spheres with periodic boundary conditions. Some representative results for large disordered disk and sphere packings are given, but more robust and efficient implementations as well as further applications (e.g., nonspherical particles) are anticipated for the future.

Fig. 7. Results from the algorithm of Section 6.1 (Algorithm 1) showing rattlers. With reasonably tight tolerances, there is no strictly jammed subpacking of this packing. Note that it may be possible to remove some of the disks from the collectively jammed subpacking and still maintain the jamming property. The dotted disks represent periodic images.

Visit http://atom.princeton.edu/donev/Packing/ for A. Donev's insightful animations.

a) Electronic mail: torquato@electron.princeton.edu