## Abstract

This article examines how 3*N* non-overlapping equal circles forming *N* triplets must be packed on a sphere to ensure that the angular diameter of the circles will be as large as possible. Furthermore, this problem is solved under the constraint that, within each triplet, the circle centres lie at the vertices of an equilateral triangle inscribed into a great circle of the sphere. Computer-generated solutions to this optimization problem are presented for *N*=2–7 triplets. The configurations obtained are characterized as compounds (nolids) of equilateral triangles.

## 1. Introduction

Many situations in the natural sciences and in technological applications can be modelled as variants of the packing problem—determining the most efficient packing of objects in an appropriate space. In a recent example, results on random close packing of equal oblate spheroids in three-dimensional space were used to give insight into the material properties of ceramics and glass-like materials (Donev *et al*. 2004). In one version of the packing problem, the task is to arrange *n* equal circles (spherical caps) without overlap on a sphere so that they have a maximum angular radius *r* (Tammes 1930). The Tammes problem has a vast literature: exact mathematical solutions exist for the range 1≤*n*≤12 and for *n*=24. An account of these results is given in Fejes Tóth's books (1964, 1972). Computer-generated putative solutions have been calculated for much larger values of *n* (Sloane *et al*. 2000), and a list of current best solutions complete to *n*=130 is maintained on the Web. In the present paper, the Tammes problem will be called the *unconstrained problem*.

In applications it can be more useful to deal with a *constrained* version of the spherical circle packing problem. For example, the arrangement of packed circles may be required to exhibit a particular overall point-group symmetry. Axially symmetric packing on a sphere has been investigated by Goldberg (1967). Families of multi-symmetric packings have been studied in tetrahedral, octahedral and icosahedral groups, (Robinson 1969; Tarnai & Gáspár 1987; Tarnai 2002) and the icosahedral solutions are tabulated to large numbers of circles (Sloane *et al*. 2000). Centrosymmetric packings, in which every circle has an antipodal partner, have been studied (Fejes Tóth 1965; Conway *et al*. 1996; Fowler *et al*. 2002). Single- and multi-stranded spiral packings have also been analysed (Székely 1974; Gáspár 1990).

The motivation of the present paper is provided by the general importance of packing and ‘polyhedral’ packing, where the circle centres are constrained to lie at the vertices of a rigid polyhedron inscribed into a sphere and the densest packing of these polyhedral units is the objective. Addition of a constraint to the problem produces numerical differences (the maximum packing radius decreases) and qualitative differences (new configurations arise). Polyhedral packings for regular tetrahedra have been studied; they give some well known and some apparently new compounds (Tarnai *et al*. 2003). These packings also show family relations between solutions for different tetrahedron numbers, *N*, in that removal of a unit from a high-symmetry solution for *N* can sometimes yield an optimum solution for *N*−1 unit, in a manner reminiscent of toppling games such as spillikins, which involve removal of sticks from a pile or bricks from a stack.

In this paper, we study an even simpler constraint, that of grouping in rigid equilateral triangles. The task is the following. How must 3*N* non-overlapping equal circles forming *N* triplets be packed on a sphere so that the angular diameter of the circles will be as large as possible under the constraint that, within each triplet, the circle centres lie at the vertices of an equilateral triangle inscribed into a great circle of the sphere? This problem will be called the *constrained problem*. It will be shown that this apparently simple problem gives rise to interesting extended relations between solutions for *N*, *N*−1 and *N*−2 triplets and produces new zero-volume compounds (or *nolids*; Holden 1991), some of which are unexpectedly non-rigid.

## 2. Method

In a packing problem for *n*=3*N* equal circles grouped as *N* equilateral triangles inscribed into great circles of the unit sphere, the positions of the circles can be described by three angular variables per triplet. Each triangle is fixed by the two polar angles of an arbitrarily chosen apical vertex together with the angle of a conical rotation about the radius vector to this apex that fixes the two base vertices. The first triangle can be fixed in a standard position (e.g. apex at the North Pole, one base vertex on the Greenwich meridian), leaving 3(*N*−1) degrees of freedom to be optimized.

Circle packing is one limit of the *intermediate* problem (Fowler & Tarnai 1996) in which *n* equal circles of radius *r* are arranged on a sphere with overlap to minimize the proportion of the spherical surface that is left uncovered. Solutions exist for a range *r*_{p}(*n*)≤*r*≤*r*_{c}(*n*), where *r*_{c}(*n*) represents the *covering limit*, in which the circles have the minimum radius necessary to ensure that every point of the spherical surface is covered by at least one circle, and *r*_{p}(*n*) represents the *packing limit*, in which the circles have the maximum radius compatible with absence of circle overlap. At intermediate *r*, the optimum solutions can be found by minimizing the penalty function, defined as the uncovered area of the spherical surface.

As in previous work (Tarnai *et al*. 2003), the strategy adopted for finding the packing radius for the constrained problem, , where , begins by solving (numerically) the constrained problem in the 3(*N*−1) angular variables, setting the initial value for *r* to the known unconstrained packing radius *r*_{p}(*n*). The radius is then decreased, re-optimizing all angles at each step. The penalty increases with falling radius and, at the point where all overlap contributions vanish, the computed penalty intersects the function 4*π*−6*Nπ*(1−cos *r*) for non-overlapping circles and the radius is . The algorithm is a downhill simplex search (Press *et al*. 1986), applied with the usual precautions against trapping in local minima.

Some definitions from the previous paper (Tarnai *et al*. 2003) on graphs, compounds, symmetry and rigidity are repeated here for comprehensiveness. A computed packing arrangement is summarized as a *packing graph*, with *vertices* representing circle centres and *edges* joining the centres of circles in contact. This graph may be embedded in three dimensions or taken as a purely combinatorial description of the packing, an *abstract packing graph*. This second graph may itself be represented on the sphere, with edge lengths idealized for maximal symmetry or in the plane as a Schlegel or similar diagram.

In the unconstrained problem, the packing graph may be fully connected or may have disconnected components, corresponding to ‘rattling’ circles that have some range of freedom of movement within an area defined by rigidly fixed circles. Rattling may also occur in the constrained problem as a concerted motion of a set of individual vertices, but there is another possibility that can produce disconnected vertices, even when all circles are fixed (Tarnai *et al*. 2003). A rigid triangular array of circles on a sphere can be fixed by a minimum of four contacts to the other circles, with no circle of the triangular set making more than two of the four necessary contacts; it may happen, for example, that two circles of a particular triplet are fixed by contacts against other rigidly fixed circles, which then fixes the third circle, even if that circle itself is out of contact with all nearest neighbours. For similar reasons, vertices of degree two or one may occur in the packing graph, which is therefore not always the skeleton of a polyhedron. It is useful to label the vertices triangle by triangle to help identify such cases. Though not all packing graphs are polyhedral, a polyhedron-like object can always be produced by taking the union of all the triangles; the resulting object is a *packing compound*. An assembly of faces that encloses no volume is termed a *nolid* by Holden (1991). All our packing compounds are nolids.

The packing *compound* has the symmetry *G*_{c} of the union of the triangles, with all edges vertices and interior points defined by the circle centres in their optimized positions. The packing *graph* embedded on the spherical surface and defined by the same optimized circle positions, but without taking account of the interior of the sphere, has point-group symmetry *G*_{p}. The *abstract* packing graph, when embedded in the same spherical surface and formed by retaining the connectivity of the packing graph but disregarding its specific geometrical properties, has a maximal symmetry *G*_{a}.

The vertices of the packing graph are the centres of the spherical circles and the edges (all of equal length) are the shorter great-circle arcs joining the centres of touching spherical circles. Danzer (1963) considered a packing graph such that its edges are free to rotate about the vertices, with lengths that can vary freely but simultaneously and in the same proportion. He defined the graph to be *rigid* if the edge system with these properties does *not* admit motions other than isometries (rigid motions). This concept of rigidity is termed *Danzerian* to distinguish it from the more generally used definition, where it is assumed that edge lengths cannot change. Danzer's idea is that if the graph is not rigid (in his sense), then, in general, the packing is not locally optimal. Since we are dealing here with graphs on the unit sphere with distances measured by angles, Danzerian-rigid graphs are permitted to slide on the spherical surface only, with three degrees of freedom: a trivial example is the regular spherical tetrahedron. Here, although each individual edge can change its length, the requirement that all edges are equal does not allow any change in the common edge length (or any other motion except rigid slides).

A packing graph may be disconnected in unconstrained packing and, hence, we discuss the rigidity of a related object—the union of edge networks of triangles and edges of the graph. Let the graph of packing have *E* edges connecting *N*>1 triangles. The generic degree of freedom, *f*, of the packing can be determined by using the Kutzbach principle (Hunt 1978). Each triangle as a rigid body on the surface of the sphere is able to move with three degrees of freedom. Each of the *E* edges represents a constraint removing one freedom. Elimination of the whole assembly's rigid motion on the spherical surface reduces the degrees of freedom by three, but simultaneous edge-length variation allows one additional degree of freedom. Counting all of these, we have for the generic degree of freedom (in the Danzerian sense)(2.1)This formula was derived by a different argument in the previous paper (Tarnai *et al*. 2003).

If *f*>0, the packing cannot be rigid in the Danzerian sense. Therefore, it is expected that the edge length of the graph will not be a local maximum and it should normally be possible to improve the packing. If there are some edges among the triangles that are isolated (rattling), then only three edges per isolated triangle contribute to *E*, as this is the number needed to connect such a triangle to the rest of the graph. All cases in the present paper were checked for Danzerian rigidity.

## 3. Results

Results for the packings of *N* triplets are presented pictorially in four different ways (figures 2–5) and summarized in table 1. Figure 1 illustrates the correspondence between the arrangement of circles (in this case for *N*=4) and the packing graph. The packing graphs embedded on the sphere are shown in figure 2 and are represented as Schlegel-like diagrams in figure 3. The triangle compounds are shown in figure 4. The same compounds, drawn to emphasize their symmetry, are shown in figure 5. Each figure lists all six cases, *N*=2–7.

The packing for *N*=1 is not considered a separate result as it is trivial, with denoting the radius at which the three circles of a single triangular triplet come simultaneously into contact along the equator. The arrangement of circles is the same in constrained and unconstrained problems and, hence, . The packing graph is an equilateral triangle (as is the abstract packing graph). The packing compound is a single triangle and all three have *D*_{3h} point-group symmetry.

### (a) *N*=2

For *N*=2 triangular triplets, the packing radius is (cf. the packing radius for the unconstrained problem, *r*_{p}(6)=45°). In a range of radii, *r*^{*}(6)>30°, the minimum-penalty configuration of the intermediate problem is unique and the contact graph consists of a non-planar folded hexagon with alternative vertices occupied by the circles belonging to each triangular triplet. For *r*^{*}(6)=45° the contact graph and the related compound are shown in figure 6*a*. As the radius is reduced, the hexagon flattens out, tending in the limit to a regular hexagon on a great circle of the sphere. Since the generic degree of freedom for this structure, which has six edges, is negative , the arrangement is expected to be rigid on the pure counting argument. However, it is clear by inspection that the regular–hexagonal configuration is non-unique: rotation of one triangular triplet about an axis connecting opposite vertices of the hexagon maintains packing, but breaks two contacts (edges of the packing graph). At all non-zero values of this rotation angle (call it *α*), the packing graph has only four edges, and is composed of two *P*_{3} subgraph components, arranged in symmetry *D*_{2} (*D*_{2d} at *α*=90°). At *α*=0°, the packing graph, abstract graph and packing compound all have *D*_{6h} symmetry. Figure 6*b*–*d* illustrate the changing packing graph and compounds as *α* changes from 0° to 90°.

We note here that, at *α*=0°, the circles belonging to the two triplets alternate along the equator of the sphere, exactly as dark and light circles alternate in figure 7, which shows a marquetry ball made in Hakone, Japan. This traditional souvenir object is produced by lathe-turning a bundle of sticks of different woods glued together. On inspection of this ball, it is easy to picture how the motion of the packing configuration takes place. Consider three consecutive circles, say two dark and one light. They lie in one hemisphere. The other three, two light and one dark, lie on the other hemisphere. The motion can be realized if one hemisphere, together with the circles on it, rotates relative to the other.

### (b) *N*=3, 4

These cases are conveniently taken together in the reverse order. The packing of *N*=4 equilateral triangles gives the assembly of four-triangles-in-a-cuboctahedron as a packing compound, noted by Holden (1991) as a ‘curious nolid’. The packing radius of (cf. *r*_{p}(12)≈31.7175°) is determined by the symmetry of the cuboctahedron. The entry for *N*=4 in figure 3 shows the packing graph superimposed on the underlying cuboctahedron in Schlegel projection; when labels are ignored, both the packing graph and the abstract packing graph have full centrosymmetric octahedral symmetry *O*_{h}. As Holden notes, the compound is chiral; it belongs to rotational subgroup *O*. The structure is highly overconstrained, , and the packing is rigid.

Removal of any one triangle from the packing for *N*=4 leaves a rigid structure which is identical to the local optimum (and conjectured global optimum) found by the programme for *N*=3. The packing graph in this case (figure 2) is a trigonal barrel with equal equilateral triangles around the poles and three inclined (and bent) staves. The packing graph and the packing compound have *D*_{3} symmetry but the abstract packing graph has the higher *D*_{3}_{h} symmetry. Since no relaxation is possible, the radius remains at 30°. Thus, we have (cf. *r*_{p}(9)≈35.2644°) and removal of any triangular triplet from the *N*=3 solution yields a particular solution for *N*=2 with angle *α*≈70.5288° determined by the geometry of the cuboctahedron.

In the entries for *N*=2, 3, 4 in figures 3 and 4, the dashed lines and the solid lines, respectively, show the edges of the master cuboctahedron into which two, three and four triangles are inscribed.

### (c) *N*=5, 6

Given their structural similarity, it is again convenient to discuss these two cases together. For five and six triangular triplets, the respective packing radii are (cf. *r*_{p}(15)≈26.8289°) and (cf. *r*_{p}(18)≈ 24.7783°). The packing graphs in both cases are barrel-like with equal regular *N*-gons around the poles and a divalent vertex on each of the *N* staves of the barrel. The entry for *N*=5 and 6 in figure 3 shows the waist of the barrel as a dashed *N*-gon inscribed into the equator connecting the divalent vertices. Each triangular triplet contributes one circle to each of the upper and lower *N*-gons and one on a stave (at the kink on the equator). The packing graph is chiral. Both packing graph and compound have *D*_{N} symmetry. The maximum symmetry group that can be taken as the symmetry of the abstract graph is *D*_{Nh}. The packing in both cases has a generic negative degree of freedom ( for *N*=5 and for *N*=6) and is found to be rigid in the Danzerian sense.

### (d) *N*=7

For seven triangular triplets, the packing radius is (cf. *r*_{p}(21)≈22.8066°). In this case, the packing graph is disconnected. Nine of the vertices form a triskelion-like cap consisting of four fused triangles and three projections occupying the northern hemisphere, nine more vertices form a copy in the southern hemisphere and the remaining three vertices lie on a great circle in the equatorial belt, constituting an isolated vertex triplet. This physically corresponds to one triangular triplet rattling within the overall packing. The entry for *N*=7 in figures 2 and 3 shows the contacts as thick lines and adds dashed lines to represent the rattling triangle. The two component subgraphs are in fact held rigidly in position by the ‘internal’ connections between the circles constituting individual triangular triplets. Only the equatorial triangle has movability, and this is limited. Again, the structure is overconstrained: . In determining *f* in this way, three new edges were added to connect the rattling triangle to the rest of the graph. Formal addition of such edges leaves *f* describing the generic rigidity of the rest of the system: the system *minus* the rattling triangle. The *f* count then tells us that the arrangement, though non-rigid with respect to this triangle, is rigid with respect to relative motion of any of the others. Both packing graph and compound have *D*_{3} symmetry, whereas the abstract packing graph has full *D*_{3h} symmetry.

## 4. Discussion

The solutions to the triplet optimization problem for *N*=3, 4, 5 and 6 all belong to one and the same structural family. For *N*=3, the packing configuration can be considered as a threefold symmetric barrel, where the three triangles are generated by rotation of one original, and the vertices of each triangle lie on three distinct latitudes (one vertex on the equator, the other two in the two hemispheres at equal distances from the equator). For *N*=4, the packing is a cuboctahedron that can be considered as a fourfold symmetric barrel, albeit with eight extra edges in the packing graph. For *N*=5 and 6, the fourfold barrel is expanded to five- and sixfold rotational symmetry, respectively. In fact, the packing for *N*=2 can also be regarded as a degenerate member of the same family as it can be generated in the same way, resulting in a twofold symmetric barrel. The angular bisector at the equatorial vertex of the original triangle is horizontal (lies in the equatorial plane) in all cases (*N*=2, 3, 4, 5 and 6), but the edges of the original triangle have different inclinations to the vertical in each case.

For the unconstrained problem, it is known that the solution for *n*=5 and 11 circles is obtained when one circle is removed from the best packing of 6 and 12 circles, respectively (Fejes Tóth 1964). We have found a similar situation here for triplet packings, in that the numerically generated best packing for *N*=2 and 3 is obtained when one triplet is removed from the best packing for three and four triplets, respectively. In these cases, similarity between the unconstrained packing and the constrained packing extends also to rigidity properties. The unconstrained best packing of 12 circles is rigid. After one of the 12 circles is removed, the packing of the remaining 11 will preserve rigidity. Similarly, the best packing of four triangular triplets is rigid and after one triplet is removed, the packing of the remaining three will also be rigid. The unconstrained best packing of six circles is rigid. After one is removed, the packing of the remaining five circles is no longer rigid. Similarly, the best packing of three triangular triplets is rigid but, after one is removed, the packing of the two remaining triplets is non-rigid. Despite their lack of rigidity, none of these packings can be improved.

Similarity exists also between the unconstrained packing of five circles and the constrained packing of two triplets, if, as in our numerical method, we approach packing from the direction of the solution to the related intermediate problem. Fowler & Tarnai (1996) have shown for *r*(5)>*r*_{p}(5) that the solution to the intermediate problem of five circles is unique, but that when the circle radius reaches the packing radius, *r*(5)=*r*_{p}(5), this property disappears and infinite optimal arrangements exist. Similarly, for , the solution to the intermediate problem of two triangular triplets is unique. When the radius reaches the packing radius, , the uniqueness of the solution is lost and there are, again, infinitely many optimal arrangements.

For the unconstrained packing problem, the packing radius typically decreases with increase in the circle number: *r*_{p}(*n*−1)>*r*_{p}(*n*). Proven exceptions are for *n*=6 and 12 where equality holds, that is, the best arrangement of *n*−1 circles is obtained by removal of one circle from the best packing of *n* circles. Some years ago, when fewer numerical results were available, Robinson (1969) thought that perhaps there were additional exceptions for *n*=24, 48, 60 and 120. Székely (1974) referred to comments by Molnár who supposed many other exceptions to exist (not only those mentioned by Robinson), did not exclude cases where *r*_{p}(*n*−*i*)=*r*_{p}(*n*) for *i*>1 and thought that 48 may have been the first value of *n* for which *i*=2. Later numerical results refuted all these suggestions and it is conjectured that the property *r*_{p}(*n*−1)>*r*_{p}(*n*) only holds for *n*=6 and 12 (Tarnai & Gáspár 1991). If this conjecture is correct, no packings exist for which . For constrained packing problems, where congruent sets of *k* circles are packed on the sphere, it also sometimes occurs that the best packing of *N*−1 sets of circles is obtained by removal of one set from the best packing of *N* sets of circles, that is, . This happens for antipodal packing (*k*=2) in the cases of *N*=3 and 6 (Fejes Tóth 1965), and for packing of tetrahedral quartets (*k*=4) in the cases of *N*=5 and 8 (Tarnai *et al*. 2003). In the present study, such cases were also found with triangular triplets (*k*=3) for *N*=3 and 4. Surprisingly, however, the removal property is valid for two consecutive values of the number of triplets, so for *N*=4. This is, therefore, the first example of a case where the radius in the best packing of *N*−2, *N*−1 and *N* sets of equal circles is equal, that is, the removal operation can be applied twice in succession. According to the conjecture, no analogous result can exist for unconstrained packing. It is not usually possible to have two consecutive optimum circle packing moves in generalized games of spillikins, but sometimes one move is possible and, in the present case, two. An interesting issue is whether a constrained problem with a longer removal sequence exists.

## Acknowledgments

The research reported here was started within the framework of the Hungarian-British Inter-Governmental Science and Technology Cooperation Programme (OMFB and British Council, TéT grant no. GB-15/98) and continued with support from OTKA grants T031931 and T046846 awarded by the Hungarian National Research Funds. T.T. thanks the President and Fellows of Magdalen College, Oxford, for the award of a Visiting Fellowship. P.W.F. acknowledges with thanks a Royal Society/Wolfson Research Merit Award.

## Footnotes

↵† Address from 1 August 2005: Department of Chemistry, University of Sheffield, Sheffield S3 7HF, UK.

- Received February 29, 2004.
- Accepted February 1, 2005.

- © 2005 The Royal Society