The Math of Social Distancing Is a Lesson in Geometry

Sphere packing might seem like a topic only a mathematician could love. Who else could get excited about finding the most efficient way to arrange circles in the plane, or spheres in space?

But right now, millions of people all over the world are thinking about this very problem.

Determining how to safely reopen buildings and public spaces under social distancing is in part an exercise in geometry: If each person must keep six feet away from everyone else, then figuring out how many people can sit in a classroom or a dining room is a question about packing non-overlapping circles into floor plans.

Of course there’s a lot more to confronting COVID than just this geometry problem. But circle and sphere packing plays a part, just as it does in modeling crystal structures in chemistry and abstract message spaces in information theory. It’s a simple-sounding problem that’s occupied some of history’s greatest mathematicians, and exciting research is still happening today, particularly in higher dimensions. For example, mathematicians recently proved the best way to pack spheres into 8- and 24-dimensional space — a technique essential for optimizing the error-correcting codes used in cell phones or for communication with space probes. So let’s take a look at some of the surprising complications that arise when we try to pack space with our simplest shape.

If your job involves packing oranges in a box or safely seating students under social distancing, the size and shape of your container is a crucial component of the problem. But for most mathematicians, the theory of sphere packing is about filling all of space. In two dimensions, this means covering the plane with same-size circles that don’t overlap.

Here’s one example of packing circles in the plane. It might remind you of the side view of a case of soda cans:

You can imagine this pattern repeating in every direction, like a tiling of the plane. The little gaps between circles mean the plane isn’t entirely covered, but that’s to be expected with circle packings. Instead, we are interested in what percentage of the plane is covered. This is known as the “packing density” of the arrangement.

The above arrangement is called a square packing, and for good reason: We can imagine the centers of the circles as vertices of squares.

In fact, the squares themselves tile the plane.

The symmetry of this tiling makes our work easy. Since these squares cover the entire plane in a regular way, the percentage of the plane covered by circles is the same as the percentage of any one square covered by circles. So let’s take a closer look at one of those squares.

Suppose that each circle has radius r. That means the square has side length 2r. Each of the four vertices of the square is covered by a quarter-circle, so the percentage of each square covered is just the ratio of the area of one full circle to the area of one square:

$latex \frac{\pi r^{2}}{(2 r)^{2}}$ = $latex \frac{\pi r^{2}}{4 r^{2}}$ = $latex \frac{\pi}{4}$ ≈ 0.7854

Each square is about 78.54% covered by circles, so by our tiling argument, the entire plane is about 78.54% covered by circles. This is the density of the square packing. (Notice how the radius r drops out of our answer: This makes sense because no matter how big the circle is, the square will still contain four quarter-circles.)

Now, if you’ve ever tried to stack soda cans on their sides like this, only to watch them slip and slide into the gaps, you know there’s another way to pack circles in the plane.

Taking a similar approach to what we did above, we can imagine the centers of the circles in this arrangement as vertices of regular hexagons.

We call this a hexagonal packing. This arrangement seems to fill in the gaps more efficiently than the square packing. To verify, let’s compare their packing densities. Just like squares, hexagons tile the plane, so we can determine this arrangement’s packing density by analyzing a single hexagon.

How much of this hexagon is covered by circles? Since the interior angle of a regular hexagon is 120 degrees, there is a third of a circle at each of the six vertices of the hexagon. That adds up to two full circles, and the one in the middle makes three. So every hexagon is covered by three circles. If each circle has radius r, that’s a total area of 3πr².

How does that compare to the area of the hexagon? A hexagon of side length s is really six equilateral triangles of side length s, each with area $latex \frac{s^{2}\sqrt{3}}{4}$. So the hexagon has area 6 × $latex \frac{s^{2}\sqrt{3}}{4}$ = $latex \frac{6 s^{2} \sqrt{3}}{4}$. Since the side length of the hexagon in our packing is 2r, its area is:

$latex \frac{6 s^{2} \sqrt{3}}{4}$ = $latex  \frac{6(2 r)^{2} \sqrt{3}}{4}$ =$latex  \frac{24 r^{2} \sqrt{3}}{4}$ = $latex 6 r^{2} \sqrt{3}$

So now we can compute the percentage of the hexagon’s area that is covered by circles (by dividing the area of three circles by the area of the hexagon):

$latex \frac{3 \pi r^{2}}{6 r^{2} \sqrt{3}}$ = $latex \frac{3 \pi}{6 \sqrt{3}}$ = $latex \frac{\pi}{2 \sqrt{3}}$= 0.9069

Each hexagon is about 90.69% covered by circles, making this a much more efficient packing than the square arrangement. (Notice how the radius of the circle again dropped out, as we should expect.) In fact, no arrangement is more efficient.

Proving this wasn’t easy: Famous mathematicians like Joseph Louis Lagrange and Carl Friedrich Gauss started the work in the late 18th and early 19th century, but the problem wasn’t completely solved until the 1940s, when all the possible arrangements — both regular and irregular — were rigorously dealt with. That it took so long to handle the problem in two dimensions, where things are relatively easy to visualize, is a warning of what’s to come in higher dimensions.

Packing spheres in three dimensions is a much more complicated problem, though it does share some features with its two-dimensional relative. For example, the two-dimensional packings we looked at are built from a single layer.

In the square packing, we put each new layer directly on top of the previous one.

In the hexagonal packing, we nestle each new layer in the gaps of the previous one.

We get different packings depending on how we put together copies of each layer.

In three dimensions, different fundamental packings arise from stacking layers like this.

This is a layer of spheres packed hexagonally, like our optimal packing of circles in the plane. Similarly, you can stack a second layer on top of this one, nestling it in the gaps between the spheres.

But the geometry is a little more complicated in three dimensions. In each layer of spheres, the distance between adjacent gaps is less than the distance between centers of spheres. So you can’t put a sphere in every gap: They would overlap. This means that gaps in the two layers line up, creating little channels through the packing.

When placing a third layer, you have two options. One is to line up the gaps and keep the channels open. Here’s a side view of the arrangement:

To keep the channels open, you place the spheres in the third layer directly above the spheres in the first, as shown above. This arrangement of spheres is called “hexagonal close-packed” (HCP), and you can see the open passageways when you look down through the packing.

The other option for the third layer is to close off the passageways. You place the spheres in the third layer directly above the gaps in the first:

It’s known as the “face-centered cubic” (FCC) or “cubic close-packed” arrangement. Looking down you can’t see through the packing.

These two similar but fundamentally different arrangements show up in chemistry, where they describe the arrangements of atoms in different materials. (For example, metals like silver and gold possess the FCC structure, while metals like zinc and titanium possess the HCP structure.) And by continuing with either pattern you can pack space with spheres: In an HCP arrangement every other layer has spheres in the exact same position, while in FCC every third layer has spheres in the same position. You can actually create infinitely many different packings by mixing the patterns up, but what’s most remarkable about the HCP and FCC patterns is that they both produce optimal packings! Not only do they have the same packing density of $latex \frac{\pi}{3 \sqrt{2}}$ ≈ 0.7405, but these are the densest possible packings of spheres in three-dimensional space. Johannes Kepler, the famous mathematician and astronomer, conjectured this in 1611, but it took until 1998 for the mathematician Thomas Hales to provide a complete proof.

The extra space to move around in three dimensions gives us more ways to efficiently pack spheres. And packing gets even more complicated as we add dimensions: There’s more room for more possibilities, and it’s also harder to visualize. Not only that, spheres get smaller in higher dimensions!

Consider a circle inscribed in a square of side length 1.

The circle has radius r = $latex \frac{1}{2}$, so the ratio of the circle’s area to the square’s area is:

$latex \frac {\pi r^2}{s^2}$ = $latex \frac{\pi\left(\frac{1}{2}\right)^{2}}{1^{2}}$ = $latex \frac{\pi}{4}$ ≈ 0.7854

Which also happens to be the density of our square packing in two dimensions.

Now consider the volume of a sphere inscribed in a unit cube.

Again the sphere has radius r = $latex \frac{1}{2}$, so the ratio of the sphere’s volume to the cube’s is:

$latex \frac{\frac{4}{3} \pi r^{3}}{s^{3}}$ = $latex \frac{\frac{4}{3} \pi\left(\frac{1}{2}\right)^{3}}{1^{3}}$ = $latex \frac{4}{3} \pi\left(\frac{1}{8}\right)$ = $latex \frac{\pi}{6}$ ≈ 0.5236

Notice that the share of the cube occupied by the inscribed sphere in three dimensions is less than the share of the square occupied by the inscribed circle in two dimensions. This pattern continues: As dimension increases, this ratio decreases. That is to say, n-dimensional spheres occupy less and less n-dimensional space as n gets bigger.

This can be shown using calculus, but we can also understand it just by thinking about the corners. In every dimension we can inscribe an n-dimensional sphere inside an n-dimensional cube. The sphere touches the faces of the cube but doesn’t reach the corners, so around every corner is a region that’s inside the cube but outside the sphere. But an n-dimensional box has 2$latex ^{n}$corners, which means that as n increases, the number of regions uncovered by the sphere grows exponentially. Not only that, the distance between the corners and the sphere grows as well. This means that in the long run the space inside the n-dimensional cube but outside the n-dimensional sphere dwarfs the space the sphere occupies.

If shrinking spheres aren’t strange enough, sphere-packing mathematicians noticed something even more surprising in dimensions 8 and 24. Spheres in those dimensions shrank just the right amount to be able to fill the gaps with new spheres, producing ultra-dense packings of those higher-dimensional spaces. These special arrangements were conjectured to be optimal, but mathematicians didn’t know for sure until 2016, when Maryna Viazovska proved it for the dimension-8 packing. Within a week, Viazovska and collaborators extended her method to prove the 24-dimensional case as well.

Viazovska’s work means that we now know the most efficient ways to pack spheres in dimensions 1, 2, 3, 8 and 24. But there’s still a lot of work to do in the other dimensions. So get out your oranges and soda cans and start experimenting. Maybe you’ll be the one to help fill in the gaps.

Exercises

1. Suppose we begin a packing of the coordinate plane as shown below, with the bottom left circle centered at (0, 0) and the bottom right circle centered at (2, 0):

Where is the center of the third circle?

2. Below is the start of a “simple cubic” packing of spheres. What is the packing density of this arrangement?

3. Here’s the start of a packing of the plane using regular octagons.

What is the density of this packing?

Answers

The centers of the circles form an equilateral triangle of side length 2.

By symmetry, the x-coordinate of the center of the third circle is 1. Since the height of an equilateral triangle of side length s is $latex \frac{\sqrt{3}}{2}s$, the height of this triangle is $latex \frac{\sqrt{3}}{2}$ ⋅ 2 = $latex \sqrt{3}$, which is the y-coordinate of the third center. Thus, the center of the third circle is (1, $latex \sqrt{3}$).

As with the square packing of circles in the plane, we can determine the packing density of this arrangement by looking at a single cube.

At each of its eight corners, exactly one-eighth of a sphere lies inside the cube. So for each cube, exactly one sphere’s worth of the interior is occupied. If each sphere has radius r, then the cube has side length 2r. This makes the packing density (the volume of the sphere divided by the volume of the cube):

$latex \frac{\frac{4}{3} \pi r^{3}}{(2 r)^{3}}$ =$latex \frac{\frac{4}{3} \pi r^{3}}{8 r^{3}}$ = $latex \frac{\pi}{6}$ ≈ 0.5236

Notice that this is the ratio of sphere to cube we found above.

Since this is essentially a square packing of octagons, we can use the approach developed earlier and look at a single square connecting the centers of four neighboring octagons.

Notice that exactly one complete octagon, cut up into four parts, lies inside the square. A regular octagon of side length s has area (2+2$latex {\sqrt{2}})s²$ (which can be found by decomposing the octagon in various ways), and there is a single square of side length s uncovered in the middle. This makes the packing density (the area of the octagon divided by the sum of the area of the octagon and the area of that single square of length s):

$latex  \frac{(2+2 \sqrt{2}) s^{2}}{(2+2 \sqrt{2}) s^{2}+s^{2}}$ = $latex \frac{(2+2 \sqrt{2})}{(2+2 \sqrt{2})+1}$ =$latex \frac{2+2 \sqrt{2}}{3+2 \sqrt{2}}$ ≈ 0.8284

It is interesting to note that this is not the densest possible packing of octagons in the plane. Can you find a more efficient packing?

Correction: July 14, 2020

This column has been revised to reflect that the arrangement of spheres in Exercise 2 is a "simple cubic" packing, not a "body-centered cubic" packing. Also, a typographical error in calculating the ratio of a sphere’s volume to a cube’s has been corrected.