COMPUTING SCIENCE

# The Science of Sticky Spheres

On the strange attraction of spheres that like to stick together

# Elevenses

To compile the catalog of 10-sphere clusters, Arkus and her colleagues had to examine more than 750,000 matrices for minimally rigid structures. The challenge of pushing the frontier out to *n*=11 was taken up by Hoy, Harwayne-Gidansky and O’Hern at Yale. They relied on many of the same methods but adopted a different approach to streamlining the algorithms. For example, they took advantage of a curious fact proved by Therese Biedl, Erik Demaine and others: Any valid packing of spheres has a continuous, unbranched path that threads from one sphere to the next throughout the structure, like a long polymer chain. This fact implies that the rows and columns of the adjacency matrix can always be rearranged so that the superdiagonal (just above and to the right of the main diagonal) consists entirely of 1s. Confining attention only to these matrices reduces the workload by a factor of 1,000 for *n*=11.

The Yale group also devised simplified rules for excluding invalid packings. And they formulated more of the geometric rules in such a way that matrices could be tested without ever having to go through the time-consuming steps of computing sphere-to-sphere distances. For example, one such exclusion rule applies to clusters that have eight spheres arranged at the vertices of a cube. No ninth sphere can touch more than four of these corner spheres; to do so, the ninth sphere would have to lie somewhere inside the cube, but there’s no room for it there. Violations of this rule can be detected merely by counting 1s in the adjacency matrix, a much quicker operation than calculating three-dimensional coordinates.

At *n*=11 the Yale group identified 1,641 distinct clusters with *C*_{11}≥27. The vast majority of these structures have exactly 27 contacts (the 3*n–*6 value), but there are 20 clusters with 28 contacts (equal to 3*n*–5) and a single packing with 29 contacts (3*n*–4). This last object, shown at right, can be understood as a further elaboration of the “floppy” cluster described above. The flexible nine-sphere structure has two square faces exposed at the surface. One of those faces is capped to form an octahedron in the sole 10-sphere cluster with 25 contacts. Capping the other square face to create a second octahedron leads to the unique 11-sphere cluster with 29 contacts.

Incidentally, there is an obvious way to add a 12th sphere to this cluster to produce a structure with 33 contacts, equal to 3*n*–3. But whether or not 33 is the highest attainable *C*_{12} value remains a matter of conjecture, because no complete survey of 12-sphere clusters has been attempted.

Even for *n*=11 it’s possible to quibble over questions of completeness and certainty. Some of the Yale results rely on a numerical algorithm to solve the system of distance equations. As noted above, when this process fails to converge, it does not unequivocally prove that no solution exists; even after many trials, there’s always a possibility that one more run with a different initial guess might succeed. In practice, the chance that a valid sphere packing might have been missed is extremely slim; whether the question is worth worrying about is perhaps a matter of differing attitudes toward rigor in mathematics and the physical sciences.

EMAIL TO A FRIEND :

**Of Possible Interest**

**Feature Article**: Restoring Depth to Leonardo’s Mona Lisa

**Perspective**: Taking the Long View on Sexism in Science

**Computing Science**: Computer Vision and Computer Hallucinations