Sign In

Communications of the ACM

Research highlights

Spherical Cubes: Optimal Foams from Computational Hardness Amplification


View as: Print Mobile App ACM Digital Library Full Text (PDF) In the Digital Edition Share: Send by email Share on reddit Share on StumbleUpon Share on Hacker News Share on Tweeter Share on Facebook
Vega Nor Improvisation, by Victor Vasarely

Credit: DavidSenouf.com

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 cacm5510_b.gif (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.

Back to Top

1. Introduction

A foam in the d-dimensional space d is a partition of d 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 d 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 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 cacm5510_d.gif. 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 WeairePhelan 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 siliconsodium 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 cacm5510_e.gif. 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). This lattice consists of the points in d-dimensional space whose coordinates are all integers. We address the following question:

Cubical Foam Problem: What is the least surface area of a bubble that partitions d-dimensional space periodically according to the integer lattice?

The Voronoi foam for the integer lattice consists of cubes of side length 1. In d dimensions, these cubes have surface area 2d. This grows linearly with the dimension, much higher than the known lower bound of cacm5510_b.gif. Are there more "spherical" cubes, which still tile by the integer lattice, but have surface area closer to that of a ball? This is the main question that we answer in this work.

The Cubical Foam Problem seems to have been first formally raised by Choe.10 Choe showed that in two dimensions, the unit square whose surface area (perimeter) is 4 is not the optimal solution. Rather, the optimal solution is the isosceles hexagon shown in Figure 2, with 120° angles, side lengths cacm5510_f.gif and cacm5510_g.gif, and perimeterabout3.864. Choegave the three-dimensional version as an open problem. Prior to our work, the best known solution was simply to add depth to the Choe hexagon, transforming it into the prism shown in Figure 2, with surface area 5.864.11

The high-dimensional version of the Cubical Foam Problem was raised by Feige et al.11 in 2007, who noted a surprising connection to a certain problem in theoretical computer science about computational hardness amplification. We shall explain the details of this connection later. A subsequent result of Raz24 on the limits of such amplification, using an idea from a related paper of Holenstein,16 provided us with the tools to solve the high-dimensional Cubical Foam Problem.

* 1.2. Our results

  • We give a probabilistic construction proving the existence of a bubble that partitions d-dimensional space according to the cubic lattice and whose surface area is at most 4cacm5510_b.gif. Thus, our bubble is nearly spherical, in the sense that its surface area is larger than that of a sphere by only a constant multiplicative factor (about 3.04). The best previous constructions had surface area proportional to d (like the cube itself has). We conclude that the optimal solution to the Cubical Foam Problem has surface area proportional to the square-root of the dimension, just as in the more general Kelvin Foam Problem. Thus in high dimensions, integer-lattice tilings are essentially as efficient as arbitrary tilings.
  • We show that our construction also yields a highly noise-resistant procedure for the rounding high-dimensional data. Specifically, we obtain a randomized procedure, which assigns each vector of real numbers x = (x1,..., xd) to a vector of integers n = (n1, ..., nd), with the following two guarantees. Each ni is always simply xi rounded up or down to its floor or ceiling integer, yet if two real vectors x, y are at Euclidean distance , then our procedure assigns them to the same integer vector except with probability at most 2 · · . Thus, if two parties get two noisy versions x, y of the same integer vector n, they will round them to the same vector with very high probability. Somewhat remarkably, the error in this natural coordination task does not depend on the dimension at all, and depends only linearly on the noise. Previously known procedures either rounded points to far off points, so that |xi ni| could be as large as cacm5510_b.gif, or separated points at distance with probability as high as cacm5510_b.gif.9,19
  • Using different (and ad hoc) methods, we give an explicit construction for the Cubical Foam Problem in three dimensions with a surface area about 5.602. This beats the surface area of the prism obtained from Choe's prism by about 4.5%.

* 1.3. Computational hardness amplification

Our method for constructing an efficient cubical foam has a surprising inspiration: the subject of computational hardness amplification in the study of the theory of computation. Consider a computational task T, such as solving a system of equations, finding the best move in a chess position, optimizing a schedule under constraints, etc. The difficulty, or hardness, of T is measured in terms of the computational resources (say the number of steps in an algorithm) required to obtain a solution of a given quality. Hardness amplification refers to methods that can be used to transform T into an even harder task, requiring even more resources. For example, one could consider the task of solving T on d inputs simultaneously. Is this d times harder, or can a clever reuse of resources allow for a computation that achieves more than what one would naively expect?

This question arises in many areas of computational theory, including cryptography, pseudorandomness, and optimization. Our foam construction is motivated by progress in understanding hardness amplification in the context of solving constraint satisfaction problems, a major topic in computer science, operations research, statistical physics, and information theory (e.g., Achlioptas et al.1). A constraint satisfaction problem is specified by a collection of constraints on n variables. For the purpose of this discussion, we shall restrict ourselves to bivariate constraints, of the form c(x, y), where each constraint c depends on only two of the n variables. A solution to the problem is a setting of the variables that maximizes the number of constraints that are satisfied. For example, the well-known graph coloring problem can be viewed as a bivariate constraint problem. Associate a single variable xv for each vertex v of the given graph and each edge {u, v} gives us the constraint xu xv. If the variables are allowed to take values from {1, 2, 3}, then the constraints are all satisfiable, if and only the graph is 3-colorable.

One way to solve a constraint satisfaction problem is to try all settings of the variables and count the number of constraints that each setting satisfies, but this method is very inefficient, requiring exponential time. If P NP, one cannot find a solution that satisfies all the constraints efficiently. A seminal hardness amplification result, the PCP Theorem,4, 5 from 1992, improved this to show that if P NP, then efficient algorithms cannot even find approximate solutions that satisfy nearly all, a (1 0) fraction of the constraints, when a solution satisfying all the constraints is known to exist. Here, 0 is a small positive constant. Indeed, the proof actually shows that it is hard to approximate even the fraction of constraints that are satisfiable.

Raz's celebrated Parallel Repetition Theorem23 from 1995 dramatically strengthened this hardness of approximation result: he showed that for every > 0, if P NP, then efficient algorithms cannot guarantee solutions that satisfy very few, an fraction of the satisfiable constraints. Raz achieves this through a transformation of constraints called parallel repetition that we describe next. Suppose we are given a set of constraints on n variables. These constraints can be used to define new constraints on nd variables as follows: Each new variable corresponds to a d-tuple of variables from the old problem. For every d-tuple of the original constraints c1, c2,..., cd, we obtain a new constraint C(X, Y)=c1(x1, y1) and.gif c2 (x2, y2) and.gif...and.gif cd(xd, yd) that can be thought of as a bivariate constraint on the variables X = (x1,..., xd) and Y = (y1,..., yd). The resulting compound constraints are said to have been obtained by repeating the original constraints d times in parallel.

If the best assignment can satisfy (1 ) fraction of the original constraints, how many constraints can be satisfied in the parallel repetition? Intuitively, one might think that the fraction of satisfiable constraints should be smaller, perhaps decay exponentially in d, since each new constraint corresponds to satisfying a set of d of the original constraints. But proving that this is true turned out to be very challenging, and counterexamples for pure exponential decay were known. In a breakthrough result, Raz showed that no assignment that can satisfy roughly (1 32)d fraction of the constraints obtained by parallel repetition, namely, some exponential decay, occurs. A key quantity of interest here is the rate of decay, namely, how "quickly" does the problem become harder, and the approximating factor decrease. Set f(d) to be the largest number for which d repetitions of a constraint satisfaction problem decreases the approximation factor from cacm5510_h.gif to some small constant, say 1/10. In this notation, Raz showed that f(d) d1/32, and left open determining the optimal dependence on d.

This result played a key role in showing that many types of problems cannot be solved by efficient algorithms (again assuming P NP). A theorem that would prove a bound of the type f(d) d was dubbed a Strong Parallel Repetition theorem, and it remained open whether such a theorem holds. Subsequent works improved Raz's bound toward such a strong theorem, first to f(d) d1/315 in general, and then to f(d) cacm5510_b.gif22 for an important subclass of constraints satisfaction problems, but the progress stopped at cacm5510_b.gif.

Feige et al.11 were the first to observe that the parallel repetition question was related to foams. They studied a particular collection of constraints called Odd Cycle constraints, and showed that for them f(d) cacm5510_b.gif. They also showed that if there is a d-dimensional cubical foam with surface area A(d), then for this constraint satisfaction problem f(d) A(d). In particular, this meant that any proof that improved on their bound would show that there is no cubical foam with surface area cacm5510_b.gif, and any Strong Parallel Repetition theorem would prove that standard cubes are essentially the best cubical foams.

Once again, Raz24 resolved the matter and showed that Odd Cycles were a counterexample to Strong Parallel Repetition. He proved that for Odd Cycle constraints f(d) cacm5510_b.gif and thus that the results of bounds f(d) cacm5510_b.gif of Feige et al.11 and Rao22 are optimal! Indeed, one can view Raz's work as constructing a discrete cubical foam, with surface area proportional to cacm5510_b.gif. A key tool used by Raz was the so-called Consistent Sampling Lemma, invented by Holenstein to prove the upper bound of f(d) d1/3 mentioned above. Raz's result inspired our construction.

Back to Top

2. An Algorithm for Building Cubical Foams

Our solution to the Cubical Foam Problem involves generalizing Raz's discrete methods to Euclidean space and opening up the proof of the Consistent Sampling Lemma. We use the "Buffon's Needle" method to estimate surface area and we optimize our results using Fourier analysis.

Before describing our "sphere-like" cubical foam, we give some motivation for its construction. As stated earlier, our construction can also be interpreted as a very noise-resistant randomized discretization procedure for rounding off vectors of real numbers to vectors of integers.

DEFINITION 1. A discretization is a mapping which assigns each point x = (x1,..., xd) isin.gif d to an integer point r = (r1,..., rd) isin.gif d, such that |ri xi| < 1 for each i. If a discretization has the property that whenever x is rounded to r, then x + s is rounded to r + s for all s isin.gif Zd, we say that the discretization is periodic. Given a periodic discretization, we define its principle bubble to be the set of points that are rounded to the origin.

The principal bubble of a periodic discretization tiles d according to the integer lattice. Thus, any periodic discretization immediately yields a cubical foam. We will in fact give a randomized procedure whose output is a periodic discretization (hence also a cubical foam). As described earlier, we say that such a procedure is noise-resistant if every two nearby points x, y isin.gif d are unlikely to be assigned to different integer points. Intuitively, we expect the bubbles produced by a noise-resistant procedure to have small surface area, because x and y are assigned to different integer points only if the line segment joining them crosses the surface of a bubble. We will later see that finding a periodic discretization in which nearby pairs x and y are usually assigned to the same integer point is very similar to a constraint satisfaction problem where every constraint involves two variables which are points in d. Indeed, Raz's analysis of the Odd Cycle constraints suggests the investigation of a related problem (which we state somewhat imprecisely for the sake of brevity): Assign each point x in the unit cube [0, 1)d a shift z isin.gif [0, 1)d in such a way that most nearby pairs of points are likely to be assigned the same shift.

The construction will be based on a carefully chosen probability distribution f on [0, 1)d. For now, we describe the construction for any distribution f and later explain how to choose the optimal f. Let fx be f translated by x, so fx is a probability density function on x + [0, 1)d; and let cacm5510_p.gifx be the periodic extension of this function, so cacm5510_p.gifx(z) = f(z + x mod 1). Holenstein's Consistent Sampling Lemma gives a method for assigning shifts to all points such that the probability x and y are assigned different shifts is essentially cacm5510_j.gif. We draw a sequence of points (Z1, H1), (Z2, H2),... such that Zi is drawn uniformly from [0, 1)d, and Hi is uniform on (0, verbar_c.giffverbar_c.gif), where verbar_c.giffverbar_c.gif denotes the maximum value of f. Each x is then assigned a shift z = Zi, where zi comes from the first pair satisfying cacm5510_p.gifx(Zi) > Hi. Thus, we are led to seek a function f for which this is small whenever x and y are nearby points.

Given a density function f and a number h > 0, consider the shape D = {x: f(x) > h} (0, 1)d together with its boundary. We call D, or a translate of D a droplet. We will want droplets to have smooth boundaries, which do not touch the boundary of [0, 1]d. For this reason, we will require that f's periodic extension cacm5510_p.gif be analytic and equal to 0 on the boundary of [0, 1]d; we will call such a density function f proper. Given a proper density function f, we can now describe our randomized algorithm for producing a periodic discretization and associated cubical foam:

Algorithm 1: Periodic discretization (and foam) construction, given f:

  1. Let all points of d be unassigned.
  2. For stage i = 1, 2,... until all points are assigned:
  1. Choose a uniformly random pair (Zi, Hi) from [0, 1)d × (0, verbar_c.giffverbar_c.gif).
  2. Let droplet Di be {x: fzi(x) > Hi}, together with its boundary.
  3. Assign all currently unassigned points in Di to (0,..., 0), and extend this assignment periodically.
  4. Color all assignments from stage i with color i.

We remark that we color all the assignments merely to aid in the analysis of the algorithm.

It is not hard to prove that this algorithm indeed ends after a finite number of stages with probability 1. It is also clear that regardless of the algorithm's random choices, it always produces a periodic discretization. Thus, the points assigned to (0,..., 0) by the algorithm always constitute a principal bubble, which partitions space according to the integer lattice.

We illustrate a sample run of the algorithm in Figure 3, with d = 2 and f(x1, x2) = 4sin2(x1) sin2(x2). The integer lattice is outlined in gray, with the origin depicted as a gray dot. The first three panels illustrate stages 1, 2, and 3 of the algorithm. In each stage, the black dot represents Zi and the black dashed line outlines the droplet Di. Colors 1, 2, and 3 are green, yellow, and red, respectively; we have used dark colors to show the points assigned to (0, 0) and light colors to show their periodic translations.

Back to Top

3. Analysis of the Algorithm

First, we compute the probability of rounding a pair of points x, y to different droplets:

THEOREM 1. Let f be a proper density function, and cacm5510_k.gif be a short line segment in d, say y = × + · u, where u is a vector of length 1, and > 0 is sufficiently small. For a given execution of Algorithm 1, let N denote the number of times cacm5510_k.gif crosses the boundary between differently colored regions. Then

ueq01.gif

where the notation means equality up to order 2.

Next, using the relationship between noise resistance and surface area we show:

THEOREM 2. Given an execution of Algorithm 1, let A denote the surface area of the boundary between color regions within [0, 1)d. Then

ueq02.gif

Finally, we find f that minimizes the noise resistance and surface area:

THEOREM 3. cacm5510_l.gif is a proper density function with verbar_c.gifcacm5510_m.giffverbar_c.gif2cacm5510_b.gif. Moreover, for each vector of unit length u, f satisfies |cacm5510_m.giff,u|2.

The bounds we obtain for our cubical foam solution and for the noise resistance of our coordinated discretization procedure follow easily from these theorems. The bubble B output by Algorithm 1 has a surface area at most 2A, where A is the quantity in Theorem 2; hence with the f from Theorem 3, the expected value of B's surface area is at most 4cacm5510_b.gif. Hence, there must exist a bubble that tiles d according to the integer lattice with a surface area at most 4cacm5510_b.gif. As for the noise resistance of Algorithm 1 as a coordinated discretization procedure, if points x, y isin.gif d at distance are assigned different integer points by the algorithm, then N, the number of times segment cacm5510_k.gif crosses the boundary between color regions, must be at least 1. The probability of this event is at most cacm5510_n.gif[N]. Combining Theorems 1 and 3, this probability is at most 2 (up to an error of 2, but this error can be eliminated) as claimed.

Next we outline the proofs of Theorems 1, 2, and 3.

We begin with the main result, Theorem 1. Let cacm5510_o.gif = closure ({x:cacm5510_p.gifZ(x)>H}) be a random "droplet pattern" as would be chosen in a single stage of Algorithm 1; that is, cacm5510_o.gif, is a random droplet along with all of its integer translations. Let I denote the event that cacm5510_o.gif intersects the segment cacm5510_k.gif, and let M denote the number of intersection points between the boundary of D and the segment cacm5510_k.gif. Since cacm5510_k.gif is very short, the first color region that touches the segment is very likely to completely enclose it. Thus, even conditioned on event I occurring, M is quite likely to be 0. More precisely, our main goal is to show that

eq01.gif

Using Equation (1), it is not hard to prove Theorem 1. To see this, consider the first stage of the algorithm's execution in which a droplet pattern touching cacm5510_k.gif is chosen. Let M1 be the number of intersections between cacm5510_k.gif and the boundary of this droplet pattern. Equation (1) tells us that cacm5510_n.gif[M1] · b. Recalling that N denotes the number of times cacm5510_k.gif crosses the boundary between differently colored regions at the termination of the algorithm, we certainly have N M1. However, it is unlikely that N will exceed M1. Indeed, consider the second stage of the algorithm's execution in which a droplet pattern touching cacm5510_k.gif is chosen, and define M2 to be the number of intersections between the boundary of this droplet pattern and cacm5510_k.gif. Again, by Equation (1) we have cacm5510_n.gif [M2] · b. But furthermore, these M2 intersections can only contribute to N if the first droplet pattern to touch cacm5510_k.gif failed to completely enclose it. The probability of this is precisely Pr[M1 > 0] cacm5510_n.gif[M1] · b. Hence, the expected contribution to N from this second stage is at most ( · b)2. Continuing the argument, we are able to upper-bound cacm5510_n.gif [N] by

ueq03.gif

We now describe the proof of Equation (1). Since the probabilistic choice of cacm5510_o.gif is invariant under any translation of d, we may assume x = 0 and hence y = · u. For a given z isin.gif [0, 1)d, let gz: [0, ] 0 denote the restriction of cacm5510_p.gifz to the line segment from 0 to · u and write G(z) = verbar_c.gifgzverbar_c.gif. The event I occurs when the randomly chosen Z and H satisfy H < G(Z), and the quantity M is equal to #{s isin.gif [0, ]: gz(s) = H}. (Here, we have discounted events with probability 0.) Hence,

eq02.gif

Regarding the denominator of this expression, G(Z) = gz(0) = f(Z) up to an additive error of order by Taylor's theorem, and hence cacm5510_q.gif up to order . As for the numerator of Equation (2), the inner integral equals the vertical distance traveled by a particle moving along the curve gz; this can be seen by partitioning the curve into small, nearly straight arcs, and considering their contribution to the integral. Hence, the inner integral equals cacm5510_r.gif. Since cacm5510_s.gif up to order on [0, ], cacm5510_t.gif up to order 2. Substituting this into the outer integral in the numerator of Equation (2), we conclude that

eq03.gif

up to order 2 as claimed in Equation (1).

To prove Theorem 2, we need a method for computing surface area. We use the following (see Santalo25)

THEOREM 4 (BUFFON'S NEEDLE THEOREM): Let S be a d-periodic piecewise smooth surface. "Drop a needle" of length 0 < < 1; i.e., let x be a random point in [0, 1)d, let u be a random vector of length 1, and let y = x + · u. If N denotes the number of intersections of the needle cacm5510_k.gif with the surface S, then

eq04.gif

where cd is the dimension-dependent-constant cacm5510_n.gif [|u1|].

Note that the value of cd is not important, as it gets cancelled out in our analysis. Given the execution of Algorithm 1, we can apply Buffon's Needle Theorem to compute the quantity A from Theorem 2. We obtain that cacm5510_n.gif [A] = cacm5510_n.gif [N]/(cd · ), where in cacm5510_n.gif [N] the probabilistic experiment is both the execution of Algorithm 1 and the random choice of the "needle." Applying Theorem 1 for each choice of the needle, we obtain

eq05.gif

up to an additive error of order . Since can be arbitrarily small, Equation (5) is in fact an exact equality. And further, for each fixed vector cacm5510_m.giff(z), the quantity cacm5510_n.gifu [|cacm5510_m.giff(z), u|] equals verbar_c.giff(z)verbar_c.gif · cd. Substituting this into Equation (5) proves Theorem 2.

It remains to prove Theorem 3. Suppose, we seek a proper density function on [0, 1)d such that verbar_c.giffverbar_c.gif is small. Writing f = g2 and using the CauchySchwarz inequality:

eq06.gif

where we also used that f = g2 = 1. Since f is a proper density function, g's periodic extension is smooth and 0 on the boundary of [0, 1]d. We may therefore rewrite g using the multidimensional sine series:

eq07.gif

Differentiating Equation (7) and applying Parseval's theorem, we get

eq08.gif

Applying Parseval to g2 = 1 yields that cacm5510_u.gif, subject to which Equation (8) is minimized when cacm5510_v.gif (1, 1,..., 1) = 1. Thus, we are led to the solution for f stated in Theorem 3 and obtain the bound verbar_c.gifcacm5510_m.giffverbar_c.gif 2cacm5510_b.gif from Equations (6) and (8). It remains to verify that |cacm5510_m.giff,u|2 also holds for each vector u. Using the CauchySchwartz inequality, we obtain

ueq04.gif

for our choice of g, and hence f. This completes the proof of Theorem 3.

Back to Top

4. A Three-Dimensional Cubical Foam

Although we have asymptotically solved the Cubical Foam Problem up to a small constant factor, in the physically natural case of d = 3, our construction does not improve on the Choe Prism, or even the cube. Here, we present an improved three-dimensional cubical foam, constructed via an ad hoc method.

The two-dimensional minimizer given by Choe in Figure 2 (left) can be described as follows: Start with a "base" facet centered at the origin; specifically, an edge from (s, s) to (s, s) for some parameter s. This already gives all vertices, by periodic extension. The hexagonal bubble is the convex hull of the two base points, their translates within [0, 1)2, and their translates by (1, 1). One chooses s to minimize the resulting surface area (perimeter).

We similarly construct a tiling shape B in three dimensions. We form a "base" facet centered at the origin, which is a regular hexagon, with vertices ±(0, t, t), ±(t, 0, t), and ±(t, t, 0), for some t isin.gif (0, 1/3). Again, this gives all vertices, by periodic extension. We take B to be the convex hull of the 6 base points, along with their 6 translates within [0, 1)3 and their 6 translates within (0, 1]3. The polytope B has 14 facets: two opposing base regular hexagons, six larger "isosceles" hexagons, and six rectangles. An illustration is in Figure 4.

One may calculate that B has a surface area

ueq05.gif

which is minimized when t 0.1880, having minimal value about 5.6121. This already beats the surface area of the Choe prism.

We can further improve this solution by letting B relax (within the torus 3/3) as a soap bubble. Using Brakke's Surface Evolver,7 we obtain the relaxed bubble B shown in Figure 4. We remark that it has slightly wavy faces and curved edges, and that the vertices have moved according to t 0.1814. The surface area of B is slightly less than 5.602, according to Surface Evolver.

Back to Top

5. Discussion

We have given a probabilistic construction of a cubical foam with near-spherical surface area. The construction uses ideas that are new to the study of foams, and is inspired by work on the limits of "hardness amplification" in certain computational optimization problems. Our construction gives the first suggestion that in high dimensions, optimal foams might not be derived from Voronoi cells and may be quite unlike polyhedra.

We have also given an algorithmic application of our foam's construction: a very "noise-resistant" procedure for rounding off vectors of d real numbers to integers. This discretization algorithm may not be practical for very large d, as Algorithm 1 is likely to run for a number of stages which is exponential in d. An important open problem is to find a coordinated discretization procedure with similar noise resistance, but taking time that grows only polynomially in d.

Finally, the construction of our cubical foam used randomness in an essential way; randomness is also used in other efficient high-dimensional constructions of foams (such as high-dimensional Kelvin foams). Although randomness is clearly required for noise-resistant coordinated discretization, it is an intriguing question as to whether it is necessary for the construction of foams, or whether explicit or derandomized constructions exist.

Subsequent to our work.17 Alon and Klartag2 gave a simpler derivation of our cubical foam via Cheeger's isoperimetric inequality; their analysis also shows that there exists a fixed parameter h that can be used as Hi throughout Algorithm 1. In other words, a good foam can be derived from the random translations of a single droplet of the form

ueq06.gif

However, it still remains unknown as to how to construct an explicit "spherical cube."

* Acknowledgments

We thank N. Alon, K. Ball, H. Cohn, P. D'Ancona, M. Goresky, J. Håstad, L. Hoffman, J. R. Lee, A. Klivans, D. Micciancio, V. Milman, O. Regev, and J. Sullivan for their insights. We thank R. Nelson for his assistance with raytracing code. Kindler was supported in part by the Koshland fellowship and by the Binational Science Foundation (BSF). O'Donnell was supported in part by NSF grants CCF-0747250 and CCF-0915893, BSF grant 2008477, and Sloan, Okawa, and von Neumann fellowships. Rao was supported in part by NSF grant CCF-1016565 and a Sloan fellowship. Wigderson was supported by NSF grants CCF-0832797 and DMS-0835373.

Back to Top

References

1. Achlioptas, D., Naor, A., Peres, Y. Rigorous location of phase transitions in hard optimization problems. Nature 435 (2005), 759764.

2. Alon, N., Klartag, B. Economical toric spines via Cheeger's inequality. 1 (Sept. 18, 2009), 101111.

3. Arnold, W.N., Lacy, J.S. Permeability of the cell envelope and osmotic behavior in Saccharomyces cerevisiae. J. Bacteriol. 131, 2 (1977) 564571.

4. Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M. Proof verification and the hardness of approximation problems. J. ACM 45, 3 (1998), 501555.

5. Arora, S., Safra, S. Probabilistic checking of proofs: A new characterization of np. J. ACM, 45, 1 (1998), 70122.

6. Ball, P. Science in culture: Beijing bubbles. Nature 448, 7151 (2007), 256.

7. Brakke, K.A. The surface evolver. Exp. Math. 1, 2 (1992), 141165.

8. Butler, G. Simultaneous packing and covering in Euclidean space. Proc. London Math. Soc. 3, 4 (1972), 721735.

9. Charikar, M., Chekuri, C., Goel, A., Guha, S., Plotkin, S. Approximating a finite metric by a small number of tree metrics. In Proceedings of 39th Annual IEEE Symposium on Foundations of Computing (1998), 379388.

10. Choe, J. On the existence and regularity of fundamental domains with least boundary area. J. Differ. Geom. 29 (1989), 623663.

11. Feige, U., Kindler, G., O'Donnell, R. Understanding parallel repetition requires understanding foams. In Proceedings of 22nd Annual IEEE Conference on Computational Complexity (2007), 179192.

12. Frank, F.C., Kasper, J.S. Complex alloy structures regarded as sphere packings. I. Definitions and basic principles. Acta Cryst. 11, 3 (1958), 184190.

13. Hales, T.C. The honeycomb conjecture. Disc. Comp. Geom. 25, 1 (2001), 122.

14. Hales, T.C. A proof of the Kepler conjecture. Ann. Math. 162, 3 (2005), 10651186.

15. Holenstein, T. Parallel repetition: simplifications and the no-signaling case. In Proceedings of 39th ACM Symposium on Theory of Computing (2007), 411419.

16. Holenstein, T. Parallel repetition: simplification and the no-signaling case. Theory of Computing 5, 1 (2009), 141172.

17. Kindler, G., O'Donnell, R., Rao, A., Wigderson, A. Spherical cubes and rounding in high dimensions. In FOCS (2008), IEEE Computer Society, 189198.

18. Kusner, R., Sullivan, J.M. Comparing the WeairePhelan equal-volume foam to Kelvin's foam. Forma 11, 3 (1996), 233242.

19. Lee, J.R., Naor, A. Extending Lipschitz functions via random metric partitions. Invent. Math. 160, 1 (2005), 5995.

20. Nielsen, L.E., Landel, R.F. Mechanical Properties of Polymers and Composites, 2nd edn, CRC Press, Boca Raton, 1993.

21. Plateau, J. Statique expÃl'rimentale et thÃl'oretique des liquides soumis aux seules forces molÃl'culaires, Gauthier-villars, Paris, 1873.

22. Rao, A. Parallel repetition in projection games and a concentration bound. In Proceedings of 40th ACM Symposium on Theory of Computing (2008), 110.

23. Raz, R. A parallel repetition theorem. SIAM J. Comput. 27, 3 (1998), 763803.

24. Raz, R. A Counterexample to Strong Parallel Repetition. IEEE Computer Society, 2008, 369373.

25. Santalo, L. Integral Geometry and Geometric Probability, 2nd edn, Cambridge University Press, Cambridge, 2002.

26. Thomson, W. On the division of space with minimum partitional area. Philos. Mag. 24 (1887), 503514.

27. Weaire, D., Phelan, R. A counterexample to Kelvin's conjecture on minimal surfaces. Phil. Mag. Lett. 69, 2 (1994), 107110.

Back to Top

Authors

Guy Kindler (guy.kindler@weizmann.ac.il), School of Computer Science and Engineering, Hebrew University of Jerusalem.

Anup Rao (anuprao@cs.washington.edu), Computer Science and Engineering, University of Washington.

Ryan O'Donnell (odonnell@cs.cmu.edu), Computer Science Department, School of Computer Science, Carnegie Mellon University.

Avi Wigderson (avi@math.ias.edu), School of Mathematics, Institute for Advanced Study.

Back to Top

Footnotes

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.

Back to Top

Figures

F1Figure 1. Four bubbles in the Kelvin Foam, formed by relaxing the Voronoi cells of the body-centered cubic lattice. Seven bubbles in the WeairePhelan Foam, formed by relaxing the Voronoi cells of the A15 Packing.

F2Figure 2. The Choe Hexagon, Choe's optimal solution to the Cubical Foam Problem in two dimensions. The hexagons extruded into three-dimensional prisms. The resulting three-dimensional cubical foam is not optimal; a solution with smaller average surface area is presented in this work.

F3Figure 3. A sample run of the algorithm, with d = 2, f(x1, x2) = 4sin2(x1) sin2(x2). The integer lattice is outlined in gray, with the origin depicted as a gray dot. The first three panels illustrate stages 1, 2, and 3 of the algorithm. In each stage, the black dot represents Zi and the black dashed line outlines the droplet Di. Colors 1, 2, and 3 are green, yellow, and red, respectively; we have used dark colors to show the points assigned to (0, 0) and light colors to show their periodic translations. In the first panel is the assignment after stage 1: all points in the dark green droplet are assigned to (0, 0); the light green translations are assigned periodically. The assignment after stage 2: the unassigned (uncolored) points within the outlined droplet are colored dark yellow and are assigned to (0, 0). The assignment after stage 3, using red. The algorithm terminates after this stageall points in 2 have been assigned. In the final panel, we outline the final bubble which partitions 2 periodically according to the integer lattice.

F4Figure 4. Our new three-dimensional cubical foam. The unrelaxed tile. The tile after it has relaxed according to Plateau's Rules. The unrelaxed tile forming a foam according to the integer lattice. Illustration of the relaxed foam as soap bubbles.

Back to top


©2012 ACM  0001-0782/12/10  $15.00

Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and full citation on the first page. Copyright for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or fee. Request permission to publish from permissions@acm.org or fax (212) 869-0481.

The Digital Library is published by the Association for Computing Machinery. Copyright © 2012 ACM, Inc.


 

No entries found