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.