## Abstract

A computer study of clusters of up to *N*=200 000 equal-area bubbles shows for the first time that partially rounding conjectured optimal hexagonal planar soap bubble clusters reduces perimeter. Different methods of creating optimal clusters are compared, and new candidate minimizers for several *N* are given.

## 1. Introduction

Soap bubbles are practical realizations of minimal surfaces in both two and three dimensions [1,2]. They are used in extinguishing fires, extracting oil from underground and also in ore separation [1], and have inspired architectural structures, including the Water Cube at the Beijing Olympics and the latest art at the New York Met [3].

The principle that governs the shape of a cluster of soap bubbles, that is, of a foam, is minimization of surface area. Yet even for planar (two-dimensional) monodisperse clusters of *N* bubbles, such as can be made between two closely spaced parallel glass plates, the perimeter-minimizing shape has been proved only for *N*≤3 [4,5] and numerically computed only for *N*≤42 (and a few other values of *N*) [6,7]. This paper addresses the asymptotic shape of such clusters as .

Determining the optimal structure of a cluster of soap bubbles may confer on it benefits in the applications described above. The optimal arrangements that we describe here also suggest the way in which deformable objects (not necessarily bubbles) should be packed so as to minimize the amount of material used to separate them. In two dimensions, these arrangements can be thought of as cross-sections through a cylindrical packing, such as tightly bundled wires, so that we give below the packing that minimizes the amount of coating necessary to separate each element.

Although the terms ‘bubble’ and ‘cell’ are often used interchangeably in describing the elements of the packings that we explore here, this hides an important distinction: soap bubbles surrounded by thin liquid films minimize their perimeter, but several living epithelial cell types, on the other hand, minimize a more complicated function of perimeter and elastic terms [8,9]. Performing a similar optimization for aggregates of biological cells is a related problem that may offer the possibility to enhance certain properties of tissues, but this is a task that we leave for future work.

When two bubbles meet, they can reduce the total (internal + external) perimeter of this nascent cluster by sharing an edge. The least-perimeter way to fill the plane with bubbles of equal area is to tile it with regular hexagons [10]. Thus, we expect the least-perimeter arrangement of a finite cluster of *N* bubbles to consist of hexagons close to the centre, with any non-hexagonal bubbles (defects) close to the periphery. Cox & Graner [11] conjectured, on the basis of the Wulff construction [12–14] and computer experiments on ‘perfect’ clusters with *N* a hexagonal number (of the form 3*i*^{2}+3*i*+1, for *i* up to 60) and a few other cases, that the shape of the periphery itself should also be hexagonal (see figure 1). Indeed, inside a hexagonal tiling, perimeter-minimizing clusters are hexagonal [15].

Morgan [16], fig. 13.1.4, on the other hand, predicted that reducing the exterior perimeter of a cluster by rounding it would eventually more than compensate for distortions to the hexagonal structure.

Here, we provide numerical evidence that partial rounding improves even perfect hexagonal clusters for *N*≥600, although we find no evidence that complete rounding to make circular clusters will ever be optimal.

## 2. Methods

There are a number of ways to tackle empirically the problem of finding the least-perimeter arrangement of *N* planar bubbles. One is to devise an algorithm that progressively shuffles a cluster of *N* bubbles, perhaps using Monte Carlo techniques and/or simulated annealing. Another is to enumerate all possible arrangements and calculate the perimeter of each; not only is this time-consuming, but the memory requirements make this prohibitive for the cluster sizes we consider here. Thirdly, as we describe here, it is possible to make an intuitive conjecture about the optimal shape of a cluster for each *N*, and then construct it and measure its perimeter.

We consider circular clusters, hexagonal clusters and hybrid clusters (defined below) of *N* bubbles. Here, we investigate *N* up to 1000, *N* a hexagonal number less than 11 000, and *N*=170 647. That is, we construct a cluster with hexagons in the bulk and the periphery of the required shape in the Surface Evolver [17], set all bubble areas to be equal (to , so that edge lengths are close to unity) and seek a local minimum of the total perimeter *P* in circular arc mode. That is, we minimize the sum of the lengths of all the edges separating bubbles, as described by Cox & Graner [11]. In practice, we start from a hexagonal cluster (e.g. with *N*=721) and eliminate one bubble at a time, using one of the protocols described below and illustrated in figure 2:

*Circular cluster*. The bubble whose centre (defined as the average of the positions of its vertices) is farthest from the centre of the cluster (defined in the same way) is eliminated.

*Hexagonal cluster*. We take *hexagonal* to mean that all shells of hexagons except the outer one must be complete. The *i*th shell of a hexagonal cluster with *N*=3*i*^{2}+3*i*+1 bubbles contains 6*i* bubbles. We consider four processes of elimination:

(i)

*spiral*hexagonal clusters, in which the outer shell is eroded sequentially in an anticlockwise manner starting from the lowest point;(ii)

*corner*hexagonal clusters, in which the corners of the outer shell are first removed and the erosion proceeds from all of the six corners;(iii)

*top-down*hexagonal clusters, in which the highest bubble in the outer shell is removed; and(iv)

*sideways*hexagonal clusters, in which the bubble furthest to the left in the outer shell is removed.

*Hybrid clusters*. To create clusters that are intermediate between a circular cluster and a hexagonal cluster, improving upon the method given by Cox & Graner [11], we consider two protocols:

(i)

*circular hybrid*, in which we start from a perfect hexagonal cluster and remove the bubbles farthest from the centre of the cluster. This process stops when the next hexagonal number is reached. (A related procedure in which a dodecagonal cluster is made by removing bubbles farthest from the centre of the cluster parallel to a line joining it to each of the six apices of the hexagonal cluster, gave similar results to the circular hybrid method but with a slightly greater perimeter for each*N*.); and(ii)

*spiral hybrid*, in which we start from a perfect hexagonal cluster but, before removing the bubbles farthest from the centre of the cluster, we first eliminate any complete rows of bubbles from the outer shell (first*i*+1, then*i*bubbles for the next four sides), in the order given by the procedure for a spiral hexagonal cluster.

## 3. Results

### (a) Comparison of methods for *N*<1000

The perimeters increase approximately as , with *k*≈3.1 [6]. Note that for each value of *N* they are all close (figures 2 and 3). So, in figure 3, we instead use what we call the reduced perimeter, . This quantity fluctuates in a saw-tooth fashion as *N* varies, but within rather narrow limits.

Different asymptotic estimates of are given by Cox et al. [6] and Heppes & Morgan [15]. The best proved general bounds on the reduced perimeter [15] are
3.1where the first expression is approximately 1.36, which is conservative, while the upper bound is precise and useful, as shown in figure 3*b*.

Patterns in the reduced perimeter are difficult to see at low *N* (figure 3*a*); the frequency is high, and circular, corner hexagonal, and hybrid clusters are often identical. Our new data agree with the candidate structure for *N*=200 (top-down or spiral hexagonal, which are equivalent here) given by Cox & Graner [11]. For *N*=50 and 100, the spiral hybrid procedure suggests new candidates: for *N*=50, a cluster which is two topological changes away from the one given by Cox et al. [6] reduces the perimeter slightly from 171.8342 to 171.8337, and for *N*=100 the perimeter is reduced from the previous conjecture of 330.880 to 330.799; the result is shown in figure 4.

For larger *N* (figure 3*b*), the reduced perimeter of a circular cluster shows the greatest fluctuation as *N* increases, with sharp upward jumps that occur roughly midway between hexagonal numbers and then a slower decay. So, we should expect that a circular cluster might have the lowest perimeter only far from hexagonal numbers, e.g. for *N*=868, which is midway between the hexagonal numbers 817 and 919 (figure 5), although even here it does not minimize the perimeter.

The spiral hexagonal cluster shows six cycles in between hexagonal numbers, making this the hexagonal cluster that is most likely to be best, since it shows the smallest deviations from a line joining the perimeters of the perfect hexagonal clusters. The spiral hybrid cluster is generally better for large *N* (figure 3*b*).

The top-down hexagonal cluster shows three cycles between hexagonal numbers with twice the height of the spiral hexagonal cluster, and turns out to be better than a spiral hexagonal cluster half the time. The sideways hexagonal cluster shows the same pattern, but shifted by the number of bubbles along one side of the hexagon (*i*, in our notation). This cluster becomes expensive when there is a half row of hexagons along one side of the cluster, an observation that also applies to the corner hexagonal cluster. A corner hexagonal cluster, obtained by removing a small number of bubbles from all six corners of the outer shell of a hexagonal cluster, is good for *N* slightly below a hexagonal number, but this cluster becomes more expensive as the number removed increases, because of the number of partial lines of hexagons in the outer shell. The reduced perimeter is similar to that of the circular cluster, in that it shows just one cycle between hexagonal numbers, but here the upward jump occurs for *N* just *above* a hexagonal number.

A circular hybrid cluster is very similar to a circular cluster for *N* less than about 200, and to a corner hexagonal cluster (figure 6) for *N* just below a hexagonal number and less than a few hundred. The difference is that after removing a few bubbles from each apex of the hexagonal cluster, the hybrid procedure allows us to remove a bubble from the next shell in. For *N* far from being a hexagonal number this method is heavily penalised, for the same reasons as for a circular cluster. As *N* increases towards a hexagonal number, there is a short interval in which a hybrid cluster can become marginally *better* than a hexagonal cluster, before the perimeter is again equal to the value in the corner hexagonal case.

In the range of *N* shown in figure 3*b*, the reduced perimeter of the spiral hybrid cluster fluctuates very little; it is between 3.09 and 3.10. This value slowly rises, which is evident only for *N*>1000 (see §3c). Spiral hybrid clusters almost always have the least perimeter in this range, beaten only by circular hybrid and corner hexagonal clusters just below a hexagonal number; this variation is because of the asymmetry in the way that the different clusters are formed, described below. Most significantly, even for hexagonal numbers, the spiral hybrid cluster can beat the perfect hexagonal cluster for *i*≥14 (*N*≥631). We have thus disproved the conjecture of Cox & Graner [11] that perfect hexagonal clusters minimize perimeter.

### (b) Influence of asymmetry

There is also a small discrepancy in the data, visible in figure 3*b*, which turns out to be significant. For *N* just below a hexagonal number, the corner hexagonal clusters and the two hybrid clusters are slightly different, although the methods described above should give exactly the same answer. The discrepancy is owing to the way in which the ‘furthest’ bubbles are removed: a small difference in the cluster ‘centre’ (either because of small shifts in the position of the whole cluster in the numerical procedure, or because there is a difference in the average position calculated on three-fold vertices or on bubbles) means that not all apices are treated equally. Figure 7 shows four different clusters of *N*=1015 bubbles, which is 12 less than the hexagonal number 1027. Instead of removing two bubbles from each corner, the asymmetric cluster created by removing three bubbles from three corners and one from the other three corners turns out to have lower perimeter.

It is therefore clear that for each *N*, there are still many possible small changes to the rounded clusters that could be tried in seeking a better minimum. Another possibility would be to extend our definition of hexagonal to allow more than one layer of bubbles to be shaved off any one of the six sides of the cluster.

In particular, our new candidate configuration for the optimal cluster of *N*=1000 bubbles, shown in figure 4*c*, has a different number of bubbles removed from each corner. It is a spiral hybrid cluster, improving upon the sideways hexagonal cluster suggested by Cox & Graner [11]. So even for *N*=1000 a little rounding of the corners of a hexagonal cluster reduces the total perimeter. Can we expect that as *N* increases further rounding reduces the perimeter even further? For *N*=10 000, we find that a circular hybrid cluster constructed by removing bubbles from the hexagonal cluster of *N*=10 267 does beat all other candidates made with the processes described here: this candidate for *N*=10 000 has *P*_{hyb-ci}=30310.532 (figure 4*d*) compared with the best hexagonal case (top-down hexagonal) with *P*_{hex-td}=30312.589 and the spiral hybrid with *P*_{hyb-sp}=30311.208. Yet this is far from being a circular cluster, suggesting that the value of *N* at which the optimal cluster might be round is much larger than 10^{3}.

### (c) When *N* is a large hexagonal number

It is clear from figure 3 that for *N* a hexagonal number the two hybrid methods give clusters that are not hexagonal but have lower perimeter than the perfect hexagonal cluster for sufficiently large *N*.

We extend the data to higher *N*, using the two hybrid methods to reduce each hexagonal cluster until *N* reaches the next hexagonal number of the form 3*i*^{2}+3*i*+1, and compare the reduced perimeters with a perfect hexagonal one. Figure 8 shows that for a sufficiently large hexagonal number *N*: (i) although the reduced perimeter of both a spiral hybrid cluster and a hexagonal cluster are increasing functions of *i*, for *N*≥631 a spiral hybrid cluster has lower reduced perimeter than a hexagonal cluster; (ii) the reduced perimeter of a circular hybrid cluster is a decreasing function of *i*, and for *N*≥4447 the reduced perimeter is lower than a hexagonal cluster; (iii) for *N*≥9919 a circular hybrid cluster has lower reduced perimeter than a spiral hybrid cluster; and (iv) the circular clusters follow a similar saw-tooth pattern as a function of *i* as for a function of *N*, and there is no evidence that the reduced perimeter decreases as *i* increases, as it would if Morgan's conjecture were correct and for sufficiently large *N* the optimal cluster were circular. Indeed, Heppes & Morgan [15], Remarks 3.2 suggest an asymptotic reduced perimeter of about 2.99. The resulting conjectured best perimeters are recorded in table 1. In summary, it appears that as *N* increases above 10 000 there is a transition to the least-perimeter cluster being produced by the circular hybrid method.

#### (i) Extending the circular hybrid method

Recall that we can use the circular hybrid method described in §2 to eliminate bubbles from a hexagonal cluster to arrive at a slightly rounded cluster with a number of bubbles that is the next lowest hexagonal number of the form 3*i*^{2}+3*i*+1. For sufficiently large *N* this procedure may be repeated, to arrive at a more rounded cluster for the next lowest hexagonal number. In the limit, we reach the circular case.

To illustrate this, we choose the value *N*=170 647 (*i*=238) to compare the effect of starting the hybrid procedure from different hexagonal clusters. For this *N*, the hexagonal cluster has *P*_{hex}=513 236.338 and a circular cluster has greater perimeter, *P*_{circ}=513 240.830. A circular hybrid cluster created from *N*=172 081 has a lower perimeter, *P*_{hyb-ci}=513 226.522, but starting from *N*=176 419 and removing the furthest 5772 bubbles from the centre gives a cluster with an even lower perimeter, *P*_{hyb-ci2}=513 224.982. This result is shown in figure 9, suggesting that the global minimum is found when the procedure starts from a hexagonal cluster that is two shells larger than required (so the minimum in the number of layers removed presumably increases very slowly with *N*). Note that the difference in perimeter is a small fraction of the total. Note also that for such large clusters, the energy minimization (gradient descent) in Surface Evolver takes approximately 3 days on a 3.10 GHz PC for each cluster.

## 4. Conclusions

We have shown that for *N* between about 600 and 11 000 the perimeter is lowest when a cluster has the shape of a hexagon with rounded corners. The conjectured optimal cluster is a spiral hybrid cluster, except for just below a hexagonal number where, depending on the asymmetry, it may also be either a top-down hexagonal or circular hybrid cluster. Even for *N* a hexagonal number, if *N*≥631 this rounding gives better candidates. Nonetheless, there is no indication in our data that a circular cluster will ever be optimal, and it remains to be determined if the limiting behaviour of a perimeter-minimizing cluster of *N* equal-area bubbles as *N* approaches infinity is circular.

## Acknowledgements

S.J.C. and F.M. acknowledge the support of the ICMS during the workshop ‘Isoperimetric problems, space-filling, and soap bubble geometry’. We thank K. Brakke for developing and distributing the Surface Evolver, and S.J.C. thanks EPSRC (EP/D071127/1) for funding.

- Received July 2, 2012.
- Accepted September 28, 2012.

- © 2012 The Author(s) Published by the Royal Society. All rights reserved.