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?)
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).
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.
N | Description |
---|---|
2 | Equator |
3 | Three meridians |
4 | Regular tetrahedon |
5 | Triangular prism? Not quite – see text. |
6 | Cube |
12 | Regular dodecahedron |
∞ | Asymptotically same performance as regular-hexagon honeycomb |
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.
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.
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_{4} 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_{4}'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_{8} 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_{8} is the optimum 8D unit-cell-volume foam.
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.
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.
The structure of the diamond (and silicon) nonlattice is points with integer coordinates with
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"?
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.
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}.