Puzzle 66: Optimal districting

Puzzle:
Divide an equilateral triangle, square, regular pentagon, regular hexagon, circle, and the surface of a sphere, into N equal-area pieces with the least cutting. (And what about "districting" in three or higher dimensions?)

Answers

Here are four theorems. The first 3 are known as Plateau rules since they apparently were first stated in an 1873 book by the blind French mathematician Joseph Plateau (1801-1883).

1. The boundary-network must consist entirely of line(geodesic)-segments and circular arcs. Proof: soap-film physics, basically. If the boundary-curve did not have constant curvature, then you could replace a short segment of it (in which the curvature was varying) by a circular arc or line segment (constant curvature) with the same endpoints and same area on each side. This would (by standard isoperimetric theorems; "Dido's problem") be shorter, a contradiction. So to avoid a logical contradiction, the boundary curves must be line segments and circular arcs only. The next two proofs will also be based on such a "reductio ad absurdam" argument; to validate the use of such a proof we also need to know that an optimum exists. That indeed is known from nontrivial but nowadays-known arguments, but we shall not prove that here, see Morgan 1994.
2. Wherever an inter-district boundary hits the boundary of the country, it must be a T-junction (perpendicular: 90-90). Proof: tiny local change near vertex to replace the last ε of length by a line segment perpendicular to the boundary, reduces length by order ε while causing area disparity of order ε², which you can fix with other changes that increase the perimeter negligibly.
3. Whenever there is a junction between three or more inter-district boundaries, it has to be three and it has to be 120-120-120 angles. Proof: a tiny local change near the vertex to replace the three-or-more curve segments within ε of it by the Steiner Minimal Tree of the points ε-away from the vertex on these curves; this reduces length by order ε while making all vertices be 120-120-120s. Although this causes an area disparity of order ε², that can be fixed with other changes that increase the perimeter negligibly.
4. At each internal vertex (and all such vertices are 3-valent 120-120-120) this equation holds: 1/A + 1/B + 1/C = 0 where A, B, C are the signed radii of curvature of the three circular arcs (and radius=∞ for a line segment, not arc). Proof sketch: this has been called "Laplace's law." Physically interpreted for "2D soap foams," see below, this states that the increase in "gas pressure" as you walk from cell 1 to cell 2 to cell 3 then back to cell 1, must be 0. Imagine the cells being filled with an incompressible fluid (to preserve cell volumes) and the boundaries being ropes with fixed tension (minimize length ⇒ minimize energy) so the min-energy geometry then has min-length. Clearly this physical problem is mathematically equivalent to our problem. Now why cannot some unphysical scenario in which two cell-boundaries of the same cell have differing pressures, be min-length? Because in incompressible unmoving fluids, the pressure is constant. So mathematically this law must hold.
5. In the asymptotic limit of a large number N of equal area regions, the minimum cut length is asymptotic to the boundary length of an N-cell regular-hexagonal honeycomb. Proof: essentially this was proved in 1999 by Thomas C. Hales in a paper available on his web page which resolved a long-open problem. Actually, Hales showed the honeycomb was the best partition of the whole infinite plane, but that does not immediately show the asymptotics when dividing some region such as a pentagon, because we also need to show the "boundary" cells can be handled still with exactly equal cell volumes for all of them. But that can plainly be done with curves drawn right with comparatively negligible length compared to the "bulk."] Hence when each cell has unit area, the total length of all the boundaries is asymptotic to 12^1/4N. In contrast, if we had (suboptimally) been using the square grid, then the total boundary length would instead have been asymptotic to 2N. That is not as good because 12^1/4≈1.8612<2. [Also – even worse – we could consider the equilateral triangle grid, which would yield boundary length asymptotic to 3^3/4N, where 3^3/4≈2.2795.] However, it is nearly as good (93%) which indicates that perfection is often not tremendously better than a decent guess.

Physics analogy: districts are cells in a soap "foam"; surface tension minimizes length of soap films; if district's area too small then increase its "gas pressure."

Using these theorems, we can find the optimum way to slice our "countries" into two, three, and four districts by exhastive examination of all possible interconnection-types. That's feasible since there are only a few for this-small N. The pictures below were produced by Eduard Baumman with some assistance from me. NOTE: these pictures have been OBSOLETED, especially T4, see Baumann's web page for the latest & corrections. Also the presumed-best circle partitions have the same structure as our best regular-hexagon partitions.

The triangular (and pentagonal) prism can be made to have 120-120-120 vertices everywhere on the sphere they are drawn on ("drawn"=radially projected onto sphere) but then the 5 (or 7) areas will be unequal. Only regular polyhedra with vertex-valencies=3 and all faces with the same number of sides – can satisfy both the all-120-degree-angles and equal areas criteria. Therefore, for each N besides 2,3,4,6, and 12, the optimal subdivision of the sphere surface must include circular arc (non-geodesic) segments.

When N=5 the best is presumably something with the same combinatorics and same symmetries as a triangular prism, but all 6 of the boundary segments separating the triangular from the quadrilateral faces are non-geodesic circular arcs (the other 3 are geodesics).

Eduard Baumann has some conjectures about some larger values of N. Some of them currently disagree with our theorems and hence are wrong. However, I have little doubt Baumann's N=6 trilaterally symmetric triangle is correct. [Can one similarly partition the equilateral triangle into 10, 15, 21, etc equal pieces using the honeycomb and presumably these are optimal for every N=n(n+1)/2, n≥1? Well, no. It stops working at N=6 and attempts to go further will generate unequal-area cells. More detail: Consider these 3 cell types: INTERIOR CELL: A regular hexagon of side=1 has area A=3sqrt(3)/2=2.598076212. All angles=120. EDGE CELL: A pentagon with angles 120,120, 120, 90, 90 and sides (starting after the first angle) 1,1,5/4,sqrt(3),5/4 also has area=3sqrt(3)/2=2.598076212. CORNER CELL: A quadrilateral with angles 90, 120, 90, 60 and sides 5/4, 5/4, 5sqrt(3)/4, 5sqrt(3)/4 has area=25sqrt(3)/16=2.706329388. Since the last area is not the same as the first two, you lose. Point is, you can't make all three cell areas equal, but you can make only two equal, so it fails if N>6.]

Probably Baumann's N=6 regular pentagon (5-way symmetry) is correct too. The optimum way to split a regular hexagon (or circle) into 7 equal pieces is almost certainly a centered regular hexagon with 6 lines emanating radially outward from its vertices, hitting the outer boundary perpendicularly. The best way to cut a disk into N pieces, N≤4, is the same as our pictures for the regular hexagon, albeit in the N=4 case with some distortion. The best way to cut a hemisphere into 6 equal-area pieces is a regular pentagon (geodesic sides, 120° angles) with geodesics – each of length half a pentagon-side – extending from the pentagon corners to the boundary of the hemisphere.

Some papers

F.J. Almgren & J.E. Taylor: The geometry of soap films and soap bubbles, Scientific American 235 (July 1976) 82-93. [gives pictures of the 10 ways to partition a sphere surface using geodesic arcs which meet at 120-120-120 junctions].

Antonio Canete: Some planar multiple isoperimetric problems, Differential geometry and its applications (Proc. Conf. Prague 2005) 129-138.

Antonio Canete & Manuel Ritoré: Least-perimeter partitions of the disk into three regions of given areas, Indiana Univ. Math. J. 53,3 (2004) 883-904.

L.Fejes Toth: Lagerungen in der Ebene, auf der Kugel und im Raum, volume 65 of Die Grundlehren der mathematischen Wissenschaften. Springer Verlag, 1953/1971. (see III.9, p.84)

L.Fejes Toth: Regular Figures, volume 48 of Int'l Monographs on Pure and Applied Math. Pergamon Press, 1964. (See 26, p.183)

L.Fejes Toth: What the bees know and what they do not know, Bulletin Amer. Math'l. Soc. 70 (1964) 468-481.

Frank Morgan: The hexagonal honeycomb conjecture, Trans. Amer. Math'l Soc. 351 (1999) 1753-1763.

Frank Morgan: Soap bubbles in R² and in surfaces, Pacific J. Maths 165,2 (1994) 347-361.

Wacharin Wichiramala: The planar triple buble problem, PhD Thesis, Univ. of Illinois at Urbana-Champaign 2002.

Finally Thomas C. Hales proved the full honeycomb conjecture in 1999: see http://www.math.pitt.edu/~thales/kepler98/honey.

Higher dimensions

The 3-dimensional analogue of the 2D hex-honeycomb is an open problem. Dublin Physicists R.Weaire & D.Phelan's foam (found in 1993) is the best known at present; it has two cell types with 12 & 14 faces respectively, all slightly curved. The Weaire-Phelan cell-centers are the black and white balls in this picture where the cubes repeat infinitely.

Whatever the optimum answer is (provided it exists), we can easily prove it consists of polyhedral cells except that the faces are not necessarily planar – they may be surfaces of constant mean curvature, e.g. spherical. But note that there are other surfaces of constant mean curvature ("minimal surfaces" in the curvature=0 case) besides spherical. Wherever faces meet (at a curve) exactly three must meet and always at 120-120-120 angles everywhere along the curve (and the curve is always a circular arc or line segment).

The Weaire-Phelan foam created quite a stir when it came out. It improved for the first time over a foam described by Lord Kelvin in 1873. Kelvin's foam has cell centers that are the points of the BCC lattice (all coordinates integers, either all-odd or all-even). If the Voronoi polyhedra of those lattice points were used, then we would get a partition with surface area [27(30√3+37)/128]^1/3≈2.657369 per unit volume. Kelvin's foam has the same combinatorial structure but has "polyhedra" with slightly bent faces; that reduces its surface area to 2.653138. (Denis Weaire tells me that "supercomputer jocks" have investigated many other 3D lattices numerically, with the nonrigorous conclusion that Kelvin's BCC lattice appears to yield the best foam.) The Weaire-Phelan foam further improves over this with 2.64417 (and even a flat-faces suboptimal version of the Weaire-Phelan foam, with 2.648475, is better than the optimally-curved Kelvin foam). It appears empirically that the Weaire-Phelan foam is the best among all foams you get by partitioning space into polyhedra with pentagonal and hexagonal faces only (no two hexagons adjacent) and then locally optimizing. (It was feasible to find that out because only 4 such polyhedral types exist. The reader is warned that all these results are numerical using Ken Brakke's evolver program and there is no proof these foams actually exist.)

With Weaire-Phelan there are two kinds of cells (equal volumes, but different shapes), and two gas pressures. It may be that Kelvin's foam is the best if we demand that all gas pressures be equal.

D.Weaire & R.Phelan: A counterexample to Kelvin's conjecture on minimal surfaces, Philos. Magaz. Lett. 69 (1994) 107-110 (also see p.99).

D.Weaire: Froths, Foams and Heady Geometry, New Scientist 21 May 1994.

D.Weaire (ed.): The Kelvin Problem: Foam Structures of Minimal Surface Area, Taylor & Francis, London 1996.

Denis Weaire & Stefan Hutzler: The physics of foams, Clarendon Press, Oxford 1999.

Another interesting remark about the Kelvin foam is that, if the gas is removed from its cells, it becomes unstable to perturbations that decrease its total area while making the cells acquire unequal volumes. [D.Levine & G.S.Grest: Philosoph. Magaz. Lett. 74 (1996) 303.] The W-P foam also is thus-unstable (more obviously). I wonder if there is any foam in any dimension≥3 which is stable in vacuum. The 2D hex honeycomb is "borderline" stable. That is, with a very small amount of gas in its cells, it is stable. (In contrast, the Kelvin & W-P foams become unstable if a small-enough amount of gas is left.)

Oddly enough, I have considerably more confidence that I know the optimal space-partition in four dimensions than I do in three! I believe the best way to partition 4-space into unit-4-volume chunks (minimizing 3D surface "area" per chunk) is the "D₄ root lattice." Its Voronoi cells are equal "24-cell" regular polytopes. Each face is a regular octahedron and each dihedral angle is exactly 120 degrees. Whenever more than 3 faces meet (at a line) we get a configuration in the 3-space orthogonal to that line, which is a perfect "carbon atom" with tetrahedral-symmetry. Finally, Ken Brakke informs me that he has recently proven that where those lines meet, this singularity too (which now, note, is genuinely 4-dimensional) is locally optimal, i.e. its surface "area" cannot be decreased by small changes. The combination of all these facts proves that this 4D foam is a "local optimum" but not our conjecture that it is the global optimum. D₄'s cell-centers are the points with integer coordinates with even sum. The cells are equal "24-cell" regular polytopes.

I also remark that it appears (there seems to be enough information to deduce this in the wikipedia article) that the "E₈ root lattice" in 8-space also has a Voronoi region (for each of its points) with all dihedral angles equal to 120°. That leads me to conjecture that the Voronoi partition induced by the points of E₈ is the optimum 8D unit-cell-volume foam.

3D Polyhedral Foam Does Not Exist

The optimal 2D honeycomb consists entirely of regular hexagons, which are convex polygons. My 4D conjectured-optimal space partition also consists entirely of convex polytopes. So it seems a distressing departure from this that in 3D, both the Kelvin and Weaire-Phelan foams do not consist of polyhedra, but instead have curved surfaces as faces. We now shall see this is logically forced:

Theorem: In a subdivision of 3-space into polyhedra of bounded (but not necessarily equal) volumes: it is impossible for all dihedral angles of all polyhedra to be 120° and for all edges to meet in "carbon-bond" local geometry. I.e: no "polyhedral foam" exists.

Proof: Any polyhedron in such a foam would necessarily be convex. Consider a corner of any such polyhedron. If it is a 3-valent corner, then by spherical trigonometry – since an equilateral spherical triangle with all angles 120° has sides whose lengths each are arcsec(-3)≈109.4712207° – that corner has an "angle defect" = 360-3×109.4712207=31.5863379°.

If it is a 4-valent corner, then, since an spherical square with all angles 120° has sides whose lengths each are arcsec(3)≈70.52877934°, that corner must have angle defect = 360-4×70.52877934=77.8848826°.

If it is a 5-valent corner, then, since an spherical pentagon with all angles 120° has sides whose lengths each are 41.81031497°, that corner must have angle defect = 360-5×41.81031497=150.9484252°.

If it is a 6-valent corner, then, since an spherical hexagon with all angles 120° (made of six spherical tringles with all angles 60°) must be planar, i.e. flat, this is not a corner at all (and corners with valence≥7 are even more impossible).

By the Gauss-Bonnet theorem, the sum of all corner angle-defects is 720°. By exhaustively enumerating every possible positive-integer linear combination of these three angle-defects, we discover that there is exactly one possibility: Any such polyhedron must have exactly 8 three-valent and 6 four-valent corners. (Note: 8[2π-3arcsec(-3)] + 6[2π-4arcsec(3)]=4π.) It then has (8×3+6×4)/2=24 edges and 12=24+2-14 faces.

One can then start enquiring about which polyhedral types have 14 faces, 24 edges, and 14 vertices (8 three-valent and 6 four-valent). Are there any? Yes. The "dual" of the "maximally-truncated cube" is one. The cube has 6 square faces. Lop off its corners by planes passing through edge midpoints; then the result has 4 square faces, 8 triangular faces, and 12 corners each four-valent. Its "dual" is the polyhedron whose vertices are the max-truncated-cube's face centers; it has 6 four-valent and 8 three-valent corners and 12 faces, each an identical rhombus. This is called a rhombic dodecahedron. Its vertices may be taken to be

There are other polyhedral types meeting our criteria. (E.g. the Voronoi cell of the HCP nonlattice packing also has 6 four-valent and 8 three-valent corners and 12 faces, with every dihedral angle 120°.) We've only emphasized the rhombic dodecahedron because it is the most symmetric one.

We can, indeed, immediately see that the rhombic-dodecahedron foam is not optimal because its edges do not meet in a perfect "carbon atom" tetrahedral configuration. (An additional Plateau rule – by far the most difficult – proved rigorously in 1976 by Jean Taylor, demands that. Jean E. Taylor: The structure of singularities in soap-bubble-like and soap-film-like minimal surfaces, Annals of Math. 103 (1976) 489-539.)

More seriously, we now shall see that no polyhedron can work. To satisfy the "carbon condition," it would be necessary to have a convex polyhedron with 14 faces, 24 edges, and 14 vertices (8 three-valent and 6 four-valent) and all its dihedrals are 120° and all its faces have all angles exactly equal to the carbon-bond angle arcsec(-3)≈109.4712207°. That forces all faces to the regular polygons (and rules out rhombi)! But are there any such polyhedra? No! We know that by consulting Johnson's list of all 92 polyhedral types with regular-polygon faces.

Norman W. Johnson: Convex Polyhedra with Regular Faces, Canadian J. Math. 18 (1966) 169-200.
Q.E.D.

Much simpler proof no 3D polyhedral foam can exist

This is trivial from the Taylor-Plateau "carbon" rule and because it is impossible to have a triangle or plane quadrilateral all of whose angles are 109.47°.

I apologize for also giving the more-complicated proof above; I did so because it leads to many interesting developments along the way.

What if we try to use the perfect carbon tetrahedra in "diamond"? No such foam exists!

The structure of the diamond (and silicon) nonlattice is points with integer coordinates with

1. all three coordinates even and sum is divisible by 4.
2. same but translated by (1,1,1).

Theorem: there is no way to get a foam with this-topology as wireframe and cells that are topologically balls.

Proof: The shortest graphical "cycles" in this wireframe are 6 edges long. if you tried to make this into a foam with hexagonal soap-film surfaces, three per bond, 4 per vertex, with each foam cell topologically a ball, then it would have hexagons as faces, three hexagons per vertex – which is not possible (Euler's theorem forces F+V=E+2 and hexagons force E=3F and trigonality forces 3V=2E so V=2F, so 3F=3F+2, oops). You could try to escape by also using some higher-gon faces, but that would only make the Euler-forced contradiction get worse: 3F=nF+2 for some real n≥3. Q.E.D.

Denis Weaire comments: This is a special case of a question that I have always wondered about because – perhaps uniquely – I worked on random covalent networks and foams:

Open question: Given a tetrahedrally coordinated network, What is the condition that it is "cellular"?

Can we prove Kelvin's is the best lattice-based foam?

A "lattice" is a set of points with (we shall demand) unit density, which is closed under vector addition.

Consider the "Voronoi diagram" of the points of a lattice. Conjecture: There is exactly one 3D lattice for which the Voronoi cell's surface area is a local minimum – the BCC lattice? I believe this conjecture could feasibly be proven as follows. Start with Voronoi's realization (in about the year 1900) that there is exactly one possible polyhedral type for a Voronoi cell of a 3D lattice (up to degeneracy), namely a centrosymmetric irregular "truncated octahedron" with 14 faces (coming as 7 pairs of identical faces) all described by a total of 6 non-negative "Voronoi parameters." Write its volume and surface area as explicit formulas in terms of these 6 parameters. Then prove the BCC lattice is the only local optimum by explicitly exhibiting finite or infinitesimal improving perturbations for all other lattices. The reason I have not already done this is that the formulas are complicated. You will need a computerized "symbolic manipulation program" to handle that complexity.

Remark: This conjecture, once proven, still would not prove Kelvin's is the best lattice-based foam, because foams have bent surfaces. But it would be suggestive.

High dimensions

I have, in work that is not yet fully written up (August 2007), proved that in D dimensions, the least-surface-(D-1)-area way to partition space into unit-D-volume cells, has surface area asymptotic (as D→∞) to (πeD/2)^1/2.

Return to puzzles

Return to main page