Spherical Cubes: Optimal
Foams from Computational
Hardness Amplification
Abstract
Foam problems are about how to best partition space
into bubbles of minimal surface area. We investigate the
case where one unit-volume bubble is required to tile
d-dimensional space in a periodic fashion according to the
standard, cubical lattice. While a cube requires surface area
2d, we construct such a bubble having surface area very close
to that of a sphere; that is, proportional to (the minimum
possible even without the constraint of being periodic). Our
method for constructing this “spherical cube” is inspired by
foundational questions in the theory of computation related
to the concept of hardness amplification. Our methods give
new algorithms for “coordinated discretization” of high-dimensional data points, which have near-optimal noise
resistance. We also provide the most efficient known cubical
foam in three dimensions.
1. intRoDuCtion
A foam in the d-dimensional space Rd is a partition of Rd into
bounded sets called bubbles. In such a foam, the bubbles are
said to tile the space. The main question studied in this work
is if a foam in Rd has only bubbles with a given volume, what
is the minimal possible average surface area of its bubbles?
This fundamental question has been a focus of study for scientists in many disciplines, from physicists studying soap
bubbles,
21 to chemists studying crystal structures,
12
biologists studying cell aggregation,
3 mathematicians studying
sphere-packings,
14 materials scientists studying polymers,
20
and even artists and architects.
6 In this work, we present
a new approach to the construction of tiling shapes, based
on methods from computer science. This approach leads
to an asymptotically optimal solution of the Cubical Foam
Problem, defined below.
1. 1. Foams
Questions about minimal surface area tilings of space have a
very long history. In the 19th century, Thomson (Lord Kelvin)
introduced the Kelvin Foam Problem,
26 which asks how
three-dimensional space can be partitioned into bubbles
of volume 1 such that the average surface area of the bubbles in the foam is minimized. This question is motivated
not only by its mathematical appeal, but also by interest in
the physics of foams in nature, since surface tension makes
bubbles seek to minimize their surface area.
One way to design foams with small surface area is to
first construct a lattice of periodically arranged points, and
90 CommuniCAtionS oF thE ACm | SePTeMbeR 2012 | VoL. 55 | no. 9
then to take the Voronoi cells around each lattice point.
The Voronoi cell of a lattice point x is the bubble, which
includes all points that are closer to x than to any other
lattice point. The solution Kelvin proposed in 1887 for his
problem was based on the Voronoi foam associated with
the so-called body-centered cubic lattice. The bubbles in
this foam have a surface area .
Kelvin further suggested letting this foam relax, so that it
conforms with Plateau’s Rules for soap bubbles21; modern
computer simulations show that this decreases the surface area to about 5.306.7, 18 In 1994, Weaire and Phelan27
exhibited a foam with an improved average surface area of
about 5.288. The Weaire–Phelan foam is formed by relaxing the Voronoi foam for a periodic subset of lattice points
(Figure 1). Weaire and Phelan used the crystal structure of
a certain silicon–sodium clathrate to choose the points. It
is still unknown whether or not their foam optimally solves
Kelvin’s problem.
It is natural to study the Kelvin Foam Problem in
dimensions other than three. In two dimensions, it was
long believed that the best solution is to tile space with
regular hexagons, which is the Voronoi foam of the triangular lattice. The optimality of this foam was conjectured
as far back as in the 4th century by Pappus of Alexandria,
but a mathematical proof was found only in 1999, by
Hales.
13 In higher dimensions, a lower bound on the average surface area follows from the Isoperimetric Inequality:
the surface area of any bubble of volume 1 must be at
least as large as that of a ball of volume 1. As the number
of dimensions d grows, this lower bound asymptotically
approaches . An upper bound that matches this
lower bound up to a factor of 2 can be obtained by taking
the Voronoi foam of a d-dimensional lattice in which the
covering-radius to packing-radius ratio tends to 2. Such a
lattice can be obtained by a probabilistic construction.
8
Hence, the minimum surface area in the d-dimensional
Kelvin Foam Problem grows in proportion to the square-root of the dimension.
In our work, we consider tilings that are periodic with
respect to the integer lattice (also known as the cubic lattice).
The original version of this paper is entitled “Spherical
Cubes and Rounding in High Dimensions” and was
published in the Proceedings of the 49th Annual IEEE
Symposium on Foundations of Computer Science, IEEE
Computer Society, 2008.