COMPUTING SCIENCE

# The Science of Sticky Spheres

On the strange attraction of spheres that like to stick together

# And Back to Geometry

How were these geometric structures determined? The key idea is to transform the adjacency matrix *A* into a distance matrix *D*. Whereas each element *A*_{ij} of the adjacency matrix is a binary value, answering the yes-or-no question “Do spheres *i* and *j* touch?,” the element *D*_{ij}* *is a real number giving the Euclidean distance between *i* and *j*.

As it happens, we already know some of those distances. Every 1 in the adjacency matrix designates a pair of unit spheres whose center-to-center distance is exactly 1; thus *A*_{ij}=1 implies *D*_{ij}=1. We even know something about the rest of the distances: A cluster is feasible only if every element of the distance matrix satisfies the constraint *D*_{ij}≥1. Any distance smaller than 1 would mean that two spheres were occupying the same volume.

To fully pin down the geometry of a cluster, we need to determine the *x*, *y* and *z* coordinates of all *n* spheres. A rule of elementary algebra suggests we would need 3*n* equations to determine these 3*n* unknowns, but in fact 3*n*–6 equations are enough. The energy of the cluster depends only on the *relative* positions of the *n* spheres, not on the absolute position or orientation of the cluster as a whole. In effect, the locations of two spheres come “for free.” We can arbitrarily assume that one sphere is at the origin of the coordinate system and another is exactly one unit away along the positive *x* axis. In this way six coordinates become fixed. Then the 3*n*–6 equations supplied by the 1s in the adjacency matrix are exactly the number needed to locate the rest of the spheres.

Having just enough constraints to solve the system of equations is more than a convenient coincidence; it’s also a necessary condition for mechanical stability in a cluster. Specifically, having 3*n*–6 contacts and at least three contacts per sphere gives a cluster a property called minimal rigidity. If any sphere had only one or two contacts, it could flap or wobble freely. Such as cluster cannot be a *max(C*_{n}*)* configuration because the unconstrained sphere can always pivot to make contact with at least one more sphere, thereby increasing *C*_{n}.

Each of the 3*n*–6 equations has the form:

defining the distance between the centers of spheres *i* and *j*. To recover the coordinates of all the spheres, this system of equations must be solved. To that end, Arkus first tried a technique called a Gröbner basis, which in recent years has emerged as a powerful tool of algebraic geometry. The method offers a systematic way to reduce the number of variables until a solution emerges. An implementation of the Gröbner-basis algorithm built into a computer-algebra system was able to solve the *n*=7 equations, but it became too slow for *n*=8.

Another approach relies on numerical methods that converge on a solution by successive approximation. The best-known example is Newton’s method of root-finding by refining an initial guess. Arkus found that the numerical techniques were successful and efficient, but she was concerned that they are not guaranteed to find *all* valid solutions. (Whenever the algorithm converges, the result is a correct solution, but failure to converge does not necessarily mean that no solution exists; it’s also possible that the initial guess was in the wrong neighborhood.)

Setting aside the algebraic and numerical techniques, Arkus chose to rely on geometric reasoning both as a guide to assembling feasible clusters and as a means of excluding unphysical ones. A basic rule for unit spheres states that if *i* touches *j*, then *j*’s center must lie somewhere on a sphere of radius 1 centered on *i*—the “neighbor sphere.” If *k* touches both *i* and *j*, then *k*’s center must be somewhere on the circular intersection of two neighbor spheres. If *l* touches all three of *i*, *j *and *k*, the possible locations are confined to a set of two points. With a handful of rules of this general kind, it’s always possible to solve for the unknown distances in a distance matrix—assuming that the adjacency matrix describes a feasible structure.

Other geometric rules can be applied to prove that certain classes of adjacency matrices cannot possibly yield a physical sphere packing. For example, if spheres *i*, *j *and *k* all touch one another, they must form an equilateral triangle. If the pattern of 1s in the adjacency matrix shows that more than two other spheres also touch *i*, *j *and *k,* then the cluster cannot exist in three-dimensional space. The unphysical matrices can be eliminated without even exploring the geometry of the clusters.

Arkus also made use of the Geomags construction set to check the feasibility of certain sphere arrangements. The Geomags set consists of polished steel balls and bar-magnet struts encased in colored plastic; all the struts are the same length, and so they can readily be assembled into a skeleton of unit-length bonds between sphere centers. Having a three-dimensional model you can hold in your hand is a great aid to geometric intuition.

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