COMPUTING SCIENCE

# The Science of Sticky Spheres

On the strange attraction of spheres that like to stick together

# Sticky Spheres

One way to solve sphere-packing problems is to view the spheres as particles subject to a physical force. Then, through mathematical analysis or computer simulation, you can try to find the geometric arrangement that minimizes the potential energy of the system. The force is usually defined as a smooth function of distance. When two particles are far apart, the force between them is negligible; at closer range the force becomes strongly attractive; at even smaller distances a “hard-core repulsion” prevents the spheres from overlapping. Under a force law of this kind, the particles settle into equilibrium at some small but nonzero separation.

The contact-counting problem can be translated into the language of forces and energy, but the physics of the system is rather peculiar. To begin with, the force law is not a smooth function of distance. Instead of hills and valleys representing gradual changes in energy, there is a sheer cliff, where the energy jumps abruptly. Imagine two spheres drifting through space. As long as they do not touch, there is no force acting between them—neither attraction nor repulsion. If the spheres happen to come in contact, however, they stick together; suddenly, the force becomes attractive. Yet any attempt to push them still closer is met by infinite resistance.

In this world of sticky spheres, the forces at work are not merely short-range but zero-range. (Martin Gardner once suggested a model for such systems: ping-pong balls coated with rubber cement.) Two spheres lower their total energy when they touch, and energy has to be supplied to pull them apart; but once they are separated, they have no further influence on one another. Minimizing the potential energy of the whole system means maximizing the number of contacts.

The discontinuous nature of the force law affects the choice of mathematical tools for solving the sticky-sphere problem. With a smooth force law, sphere-packing problems can be solved by optimization methods. An algorithm repeatedly attempts to reduce the total energy by making small adjustments to the particles’ positions, continuing until no further progress is made. This scheme won’t work with sticky spheres because there are no smooth gradients to guide the particles toward lower-energy configurations. For this reason, the sticky-spheres problem has seemed harder than most other sphere-packing tasks.

On the other hand, the discrete, all-or-nothing character of the sticky-spheres potential also brings an important advantage. Because each pair of spheres is either touching or not, the number of essentially different configurations is finite. In principle, you can examine all these possibilities and simply choose the one with the most contacts and hence the lowest potential energy. It was this insight—the idea that the problem can be solved by exhaustive enumeration—that led to the recent results of the Harvard and Yale groups.

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