The Math of Reopening Offices Requires Social Distance Geometry

Remember back in school when those in the liberal arts consoled themselves with the belief that they'd never have to use geometry in real life? JL

Patrick Honner reports in Quanta:

Determining how to safely reopen buildings and public spaces under social distancing is 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. 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.

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.

Graphics by Samuel Velasco/Quanta Magazine

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:

πr2(2r)2 = πr24r2 = π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 s23√4. So the hexagon has area 6 × s23√4 = 6s23√4. Since the side length of the hexagon in our packing is 2r, its area is:

6s23√4 = 6(2r)23√4 =24r23√4 = 6r23–√

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):

3πr26r23√ = 3π63√ = π23√= 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 π32√ ≈ 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 = 12, so the ratio of the circle’s area to the square’s area is:

πr2s2 = π(12)212 = π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 = 12, so the ratio of the sphere’s volume to the cube’s is:

43πr3s3 = 43π(12)313 = 43π(18) = π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 2ncorners, 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.