Spherical cubes
Guy Kindler, Anup Rao, Ryan W. O’Donnell, Avi Wigderson · Communications of the ACM · 2012
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 2 d , we construct such a bubble having surface area very close to that of a sphere; that is, proportional to √d (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.