COMPUTING SCIENCE

# The Science of Sticky Spheres

On the strange attraction of spheres that like to stick together

# The Well-Connected Cluster

In building clusters and counting contacts, it’s convenient to work with *unit spheres*, which have a diameter of 1 and thus a radius of 1/2. When two unit spheres are touching, the center-to-center distance is 1. The diagrams accompanying this column show a unit-length rod connecting the centers of spheres when they are in contact. Some physical models of clusters (including Geomags) keep this skeleton of connecting rods and omit the spheres altogether.

In any cluster of *n* spheres, let *C*_{n} denote the total number of contact points; then *max(C*_{n}*)* is the highest value of *C*_{n} found among all *n*-sphere clusters.

For the smallest values of *n*, finding *max(C*_{n}*)* is easy. The case of *n*=1 is trivial: A single, isolated sphere doesn’t touch anything, and so *max(C*_{1}*)*=0. Two spheres can meet at only one point, which means that *max(C*_{2}*)*=1. For three spheres the best solution puts the sphere centers at the vertices of an equilateral triangle; in this arrangement there are three contact points, and thus *max(C*_{3}*)*=3. A fourth sphere can be placed atop the triangle to create a regular tetrahedron with six pairwise contacts: *max(C*_{4}*)*=6.

Not only is it easy to construct these small clusters; it’s also easy to prove that no other *n*-sphere configurations could have a higher *C*_{n}. The reason is simply that in these clusters each sphere touches every other sphere, and so the number of contacts could not possibly be greater. In the terminology of graph theory, the cluster is a *clique*. The number of contacts in a cliquish cluster is *n*(*n*–1)/2. The sequence begins 0, 1, 3, 6, 10, 15, 21….

Going on to *n*=5, cliquishness is left behind: In three-dimensional space there is no way to arrange five unit spheres so that they all touch one another. If such a five-sphere clique existed, it would have 10 contact points. The best that can actually be attained is *C*_{5}=9, which is the number of contacts formed when you attach a fifth sphere to any face of a tetrahedral cluster. The resulting structure is known as a triangular dipyramid.

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