Least-perimeter partition of the disc into $N$ regions of two different areas

This paper presents conjectured candidates for the least-perimeter partition of a disc into up to ten regions of two distinct areas by enumerating three-connected simple cubic graphs, numerically evaluating their perimeters across various area ratios, and interpolating the results to identify optimal structures for different configurations.

The Gist

Imagine you have a round pizza (a disc) and you want to slice it up into $N$ pieces. But here's the twist: you don't just want to slice it; you want to slice it in the most efficient way possible.

In the world of physics and math, "efficient" usually means using the least amount of crust (perimeter) to separate the slices. This is like trying to build a fence around several gardens using the absolute minimum amount of fencing material.

This paper tackles a specific, tricky version of that problem:

1. You have a fixed number of slices ($N$, from 4 to 10).
2. The slices can only be two different sizes: "Big" and "Small."
3. You want to know: What is the best way to arrange these Big and Small slices so the total fence length is as short as possible?

The Rules of the Game (Plateau's Laws)

Nature loves efficiency. If you blow bubbles, they naturally snap into shapes that use the least surface area. The paper relies on Plateau's Laws, which are basically the "rules of the road" for bubbles:

• Curved Roads: The lines separating the slices aren't straight; they curve slightly (like a gentle arc).
• Three-Way Intersections: Wherever three slices meet, they do so at a perfect 120-degree angle (like a Mercedes logo).
• No Dead Ends: You won't find a slice that is just a thin, lonely sliver touching the edge; nature hates that because it's wasteful.

The Detective Work: How They Solved It

The authors didn't just guess. They acted like digital architects and detectives:

1. The Blueprint Phase (Graph Theory):
   First, they imagined all the possible "skeletons" or blueprints for the pizza. They used computer software to list every possible way to connect the dots (vertices) and lines (edges) without breaking the rules. Think of this as listing every possible way to draw a map of a city before you even build the roads.

2. The Simulation Phase (The "Surface Evolver"):
   Once they had the blueprints, they fed them into a powerful computer program called Surface Evolver. This program acts like a virtual wind tunnel or a soap-film simulator.

   • It takes a blueprint.
   • It assigns specific sizes to the "Big" and "Small" slices.
   • It lets the slices wiggle and push against each other until they find their most relaxed, energy-saving shape.
   • It measures the total length of the "fences" (perimeter).

3. The Sorting Phase:
   They ran this simulation thousands of times for different numbers of slices ($N=4$ to $10$) and different size ratios (e.g., Big slices being 2x, 4x, or 10x the size of Small slices). They then compared the results to see which arrangement won the "Least Fence" prize.

The Big Discoveries

Here is what they found, explained simply:

• Small Numbers are Simple: If you have 4 or 5 slices, the best arrangement doesn't change much, even if you make the "Big" slices huge. The structure is stable.
• Big Numbers get Complicated: As you add more slices (6, 7, 8, etc.), the "best" shape changes depending on how big the size difference is.
  • The "Clumping" Effect: When the size difference is small (the Big slices are only slightly bigger than the Small ones), the Small slices tend to huddle together in a cluster, like a group of friends at a party.
  • The "Sorting" Effect: When the size difference is huge (the Big slices are massive), the Small slices get pushed apart and separated by the Big slices, like islands in a sea of large landmasses.
• The Tipping Point: There is a specific "tipping point" (a critical ratio) where the structure suddenly snaps from one arrangement to another. It's like a puzzle piece clicking into a new position. For example, with 7 slices, if the size ratio gets high enough, a tiny slice might suddenly jump from the edge of the pizza to the very center to save space.

Why Does This Matter?

You might wonder, "Who cares about pizza slices?"

This isn't just about food. This math explains:

• Foams and Bubbles: How soap bubbles pack together in a foam.
• Materials Science: How to design lightweight, strong materials (like the "Water Cube" in Beijing, which uses a similar bubble-like structure).
• Biology: How cells pack together in tissues.

The Bottom Line

The authors created a "cheat sheet" for the most efficient way to partition a circle into mixed-size regions. They found that nature is smart but fickle: the best shape depends entirely on the balance between the sizes of the pieces. Sometimes it's best to group the small ones together; other times, it's best to spread them out.

They didn't just find one answer; they found a whole family of answers that change as the "Big" and "Small" sizes change, giving us a deeper understanding of how nature minimizes waste.

Technical Summary

Here is a detailed technical summary of the paper "Least-perimeter partition of the disc into N regions of two different areas" by F. J. Headley and S. J. Cox.

1. Problem Statement

The paper addresses the geometric optimization problem of partitioning a unit disc into $N$ regions ($N \le 10$) such that the total perimeter is minimized, subject to the constraint that the regions can only take one of two possible areas (a "bidisperse" system).

• Context: This extends the classical isoperimetric problem and the Kelvin problem (minimizing surface area in 3D) to 2D domains with fixed boundaries and unequal region sizes.
• Challenge: Unlike the monodisperse case (equal areas), where optimal structures are often unique or well-understood, allowing unequal areas introduces a vast combinatorial space of topological configurations. The difficulty lies in determining which specific graph topology and area assignment yields the global minimum perimeter for a given area ratio ($A_r$).
• Objective: To systematically enumerate all candidate topologies, minimize their perimeters numerically, and identify the optimal configuration across a range of area ratios ($A_r = 1$ to $10$).

2. Methodology

The authors employ a hybrid approach combining combinatorial graph theory with numerical energy minimization.

A. Graph Enumeration

• Theoretical Basis: Based on Plateau's laws, optimal partitions in 2D consist of circular arcs meeting at $120^\circ$($2\pi/3$) at triple vertices. This implies the underlying structure is a simple, three-regular (cubic), three-connected planar graph.
• Assumptions:
  • The partition is connected.
  • The graph is simple (no multiple edges between the same vertices) and three-connected (removing two vertices does not disconnect the graph). Non-simple or two-connected structures can be topologically rearranged to reduce perimeter.
• Generation: The authors use the software CaGe to generate all unique graphs for $N$ from 4 to 10.
• Area Assignment: For each graph, they assign areas to regions.
  • For even $N$: $N/2$ regions of Area 1 and $N/2$ regions of Area 2.
  • For odd $N$: Two cases are considered: $(N+1)/2$ large regions vs. $(N-1)/2$ small regions, and vice versa.
  • All permutations of area assignments are tested (redundant symmetric cases are handled).

B. Numerical Minimization

• Software: The Surface Evolver is used to minimize the total edge length (perimeter) subject to area constraints.
• Process:
  1. Graphs are converted to Evolver input files where edges are circular arcs.
  2. The system is confined within a unit-area circular boundary.
  3. Minimization routines find the equilibrium configuration.
  4. Topological Changes: If an edge shrinks below a critical length ($l_c = 0.01$), the topology is allowed to change (e.g., a vertex moving to the boundary or edges collapsing). This prevents the software from getting stuck in non-optimal local minima associated with unstable four-fold vertices.
• Sampling Strategy:
  • Initial minimization is performed at discrete area ratios: $A_r = 2, 4, 6, 8, 10$.
  • Interpolation: To find critical transition points, the authors take the best candidates from the discrete steps and vary $A_r$ in small increments (0.05) to track perimeter changes and detect topological transitions.

3. Key Contributions

1. Systematic Enumeration: The first comprehensive enumeration of all simple, cubic, three-connected planar graphs for $N \le 10$ applied to bidisperse partitions.
2. Combinatorial Scaling: Demonstrated the rapid growth of the solution space. For $N=10$, there are 1,249 unique graphs, leading to 314,748 distinct candidate configurations (permutations of area assignments) to evaluate.
3. Transition Mapping: Mapped the critical area ratios ($A_r$) at which the optimal topology changes for each $N$.
4. Polydispersity Analysis: Introduced a metric to analyze how the distribution of small vs. large regions affects the perimeter and structural clustering.

4. Results

The study reveals that the optimal topology is highly sensitive to the area ratio ($A_r$) and the number of regions ($N$).

• Low $N$ (4 and 5):
  • The optimal topology remains constant regardless of the area ratio.
  • For $N=5$, the optimal structure never contains an internal region; the internal vertices connect directly to the boundary.
• High $N$ (6 to 10):
  • Multiple Transitions: As $N$ increases, the number of topological transitions increases. The optimal structure changes multiple times as $A_r$ varies.
  • Critical Ratios: Most transitions occur at intermediate area ratios ($2.5 < A_r < 4$).
  • Specific Cases:
    • $N=6$: One transition at $A_r \approx 2.6$.
    • $N=7$: The case with 4 large regions ($7_{43}$) has one transition ($A_r \approx 2.8$), while the case with 3 large regions ($7_{34}$) shows a transition at a surprisingly high ratio ($A_r \approx 8.4$).
    • $N=9$ and $10$: Show the most complex behavior, with up to 5 different optimal topologies found across the range of$A_r$.
• Clustering vs. Separation:
  • Low $A_r$ (Small area difference): Smaller regions tend to cluster together.
  • High $A_r$ (Large area difference): Smaller regions tend to be separated by the larger regions.
  • This is quantified by the proportion of edges separating large and small regions ($E_{LS}$), which increases with $A_r$ for $N \ge 6$.
• Monodisperse Recovery: At low area ratios ($A_r \to 1$), the results correctly converge to the known optimal monodisperse partitions.

5. Significance and Implications

• Foam Physics: The results provide a rigorous basis for understanding bidisperse foams in 2D, which are relevant to material science, metallurgy, and biological tissues.
• Design and Engineering: The identified structures offer potential templates for lightweight, strong architectural designs (similar to the Water Cube) that utilize fixed boundaries and mixed material properties.
• Generalizability: The authors note that the methodology translates directly to the surface of a sphere. The candidates for a disc with $N$ regions correspond to candidates for a sphere with $N+1$ regions (where the disc boundary becomes the $N+1$-th region). Preliminary findings suggest sphere partitions differ from disc partitions, even in the monodisperse case.
• Complexity Management: The paper demonstrates that while the number of candidates explodes combinatorially, numerical minimization combined with smart sampling (interpolation between discrete ratios) is an effective strategy for finding global optima in complex geometric optimization problems.

In summary, this work provides a complete map of the "phase diagram" for least-perimeter disc partitions with two area sizes, revealing a rich landscape of structural transitions driven by the interplay between area ratio and topological constraints.