The shapes the optimum has

When symmetry costs asked what requiring a circle packing to be symmetric does to it, measured against an unconstrained search at equal effort, and found that a smaller space is sometimes worth searching. This rung asks the question the other way round: at which flap counts, and what decides it.

What the constraint actually is #

Packing is the hard part of the tree method, and it is the step this rung constrains. A packing of n equal discs in a square has 2n coordinates. Requiring it to be its own mirror image in the vertical centre line leaves about n of them: the discs come in pairs, one of each pair is placed and the other follows, and any disc left over has to sit on the mirror line where it has one coordinate rather than two.

So the constraint is not a penalty added to the objective. It is a reduction in dimension, and the search that runs under it is a search of a smaller space.

That is why the naive statement — a constrained optimum cannot beat an unconstrained one — is true and beside the point. It is true about the optima. The two searches are given the same number of restarts and the same number of steps, and what they return is not the optimum but the best either happened to find, so a smaller space searched at the same effort can and does win.

Where it costs and where it pays #

Under a mirror, the cost runs from 14.6 per cent at two discs down to −0.02 per cent at five. It is 10.8 per cent at eight and 10.4 at nine, 5.6 at six, 4.7 at ten, 2.8 at eleven, half a per cent at seven and a hundredth at four.

Two discs is the extreme and it is easy to see why: the best packing of two equal discs in a square puts them on the diagonal, which is not symmetric about a vertical mirror, so the constraint forbids the answer outright and the search returns the best of a different problem.

Five is the other extreme, and the sign of it is what makes the rung. Constrained to a mirror, the same effort finds a packing 0.02 per cent better than the free search does — because the best five-disc packing is symmetric, and searching half as many coordinates for it is easier.

Under a half-turn the alternation is sharper still. The constraint costs nothing at all at two discs — because the diagonal pair is symmetric under a half-turn, which the mirror forbade — costs 18.6 per cent at three, and pays at five and at eight.

The quarter-turn, which mostly cannot be asked #

Under a quarter-turn the discs come in orbits of four with at most one fixed point, so n must be a multiple of four or one more than a multiple of four. Six of the eleven counts tried admit no quarter-turn arrangement whatsoever, and the search says so rather than quietly returning the free answer.

At the four counts that do admit one — four, five, eight and nine — the constraint costs essentially nothing and pays slightly at five and at eight. That is the strongest form of the whole result: at a count where a highly symmetric optimum exists, the strongest constraint is the cheapest, because it reduces the search from 2n coordinates to about n / 2.

The worst entry in the table is exact #

The 18.56% is the largest cost anywhere in the census and, like the mirror’s 14.6% at two discs, it can be derived rather than searched for.

A half-turn takes discs in pairs with at most one fixed point, so three discs means one at the centre and two forming a pair. The pair goes on the diagonal, at $(r, r)$ and $(1-r, 1-r)$, and the binding constraint is each of them against the centre disc:

$$\sqrt2\left(\tfrac12 - r\right) = 2r \quad\Longrightarrow\quad r = \frac{\sqrt2 - 1}{2} = 0.20711.$$

Against the free optimum of 0.25433 that is a shortfall of 18.57%, which is the measured 18.56% with the search’s last digit of slack in it.

And it is the five-disc packing wearing three discs #

The closed form carries a second observation the table cannot show. $(\sqrt2 - 1)/2$ is exactly the optimal radius for five equal discs in a unit square — four in the corners and one at the centre.

That is not a coincidence: the half-turn’s fixed point forces a disc to the centre, and a central disc against a diagonal one is the same binding contact in both problems. Constraining three discs to a half-turn hands them the radius five discs get for nothing.

Which is the sharpest available statement of what a badly matched symmetry costs. Two of the five cells are simply left empty, the scale is set as though they were not, and the design pays 18.6% of every flap’s length — a third of its paper — for a constraint that suited the count it was not applied to.

Reading the alternation #

Set the three groups beside each other and the pattern in the results is that there is no pattern.

Positive is a cost. Every column has entries of both signs, no column dominates another, and a count that is expensive under one group is often free under a different one — two discs cost fifteen per cent under a mirror and nothing at all under a half-turn, three cost under two per cent under a mirror and nineteen under a half-turn.

That is the practical content of the rung. A designer choosing a symmetry for a five-flap model can choose any of the three and gain a little; a designer choosing one for a three-flap model must not choose the half-turn; and there is no rule connecting the two cases.

Which theorem was checked, and how #

Three things.

Both searches are given the same restarts and the same steps. The comparison is worthless otherwise, and the two functions’ own defaults differ, so the numbers are passed explicitly rather than taken.

The constrained search cannot leave its constraint. A search that drifted off the symmetric set would be answering the free question and reporting it as the constrained one, which is exactly the failure that would make every cost look like zero. So the symmetric packing is parameterised by its free discs and the rest are generated, rather than being penalised for asymmetry.

A count that admits no arrangement under a group returns nothing rather than a number. That matters most for the quarter-turn, where six of eleven counts are in that position, and reporting the free answer there would produce a row that looked like a cost of zero and meant “the question was not asked”.

The free search is also checked against the published optima where they are known, so a run in which it did badly would be visible as a shortfall rather than as an apparent win for the constraint.

Why the gains are so small and the losses so large #

The asymmetry in the table has a mechanism and it is worth naming, because it is what turns the result into advice.

When the constraint is satisfied by the optimum, the constrained search is looking for the same arrangement in half the coordinates. That is easier, and the gain is whatever the extra ease is worth — which for a search that was already finding the optimum most of the time is close to nothing. The ceiling on the gain is the free search’s own shortfall, which is small.

When the constraint is violated by the optimum, the constrained search is looking for the best member of a family that excludes the answer. The loss is then the real gap between the constrained optimum and the free one, which is a property of the problem and has no reason to be small — fifteen per cent at two discs, nineteen at three under a half-turn.

So the bet is bounded above by a search’s inefficiency and bounded below by a geometric gap. That is a bad shape for a bet and it is why the honest recommendation is to impose a symmetry for reasons other than efficiency.

Where the model stops #

Everything here is about equal discs, which is the case where the optima are published and the comparison can be anchored. A real design’s flaps differ in length, so its discs differ in radius, and the symmetric case there is a different problem — one whose optima are not tabulated anywhere.

Nothing here is about the rivers either. A real tree has edges as well as leaves, and a river is the general case a circle is a special case of; the symmetric version of a river packing is a different problem again and this census does not touch it.

Nothing here is about why an optimum is symmetric. That is a question about the packing problem’s own structure, and the answers for small counts are known individually rather than in general; there is no rule that says which n have symmetric optima, which is precisely why a designer cannot use the result predictively.

And the searches are searches. Getting close instead of getting it right is this site’s essay on what that costs, and everything in this one inherits it: a difference of a tenth of a per cent between two searches is a difference between two runs, not between two problems.

The other thing a smaller space buys #

There is a second reason a constrained search can win and it is not about dimension at all.

An optimiser that restarts from random positions is exploring a landscape with many local optima, and the number of them grows with the dimension. Halving the coordinates does not merely halve the volume to cover; it reduces how many places a search can get stuck. So the constrained search wins twice over when it wins: it covers more of a smaller space, and the space it covers is less rugged.

That is consistent with what the table shows — the gains are small and reliable rather than occasional and large — and it is not separable from the volume effect by anything measured here. Distinguishing them would need a search whose restarts and steps were varied independently, which is a straightforward experiment and is not this one.

What the picture cannot show #

A bar of −0.04 per cent and a bar of 14.6 per cent share an axis, and the small ones are invisible next to the large. That is honest and it is unhelpful: the interesting rows of every one of these figures are the ones near zero, and they are the ones a reader cannot see.

Nothing shows the search. The whole argument is about what a fixed budget of effort buys in spaces of two different sizes, and effort is not a thing a picture of a packing contains.

What symmetry does to the rest of the design #

The packing is one step of the tree method and the symmetry does not stop there, which is worth following through because it changes what the ten per cent is being compared against.

A symmetric packing produces a symmetric set of ridge and hinge creases, because those are derived from the packing by a construction that commutes with turning the sheet. So the whole crease pattern inherits the symmetry, and so does the base, and so does the folded model.

That has three consequences a designer cares about and none of them is efficiency. The pattern has half as many distinct creases to draw and check, which matters more on a grid than off one because error propagation is what a grid is bought for. The folding sequence has half as many distinct steps, because the two halves are folded the same way. And errors are visible: a symmetric model that has gone wrong on one side does not match itself, which is a check nothing else in the method provides.

Against that, ten per cent of paper is not obviously a bad trade. The rung’s contribution is to say what the trade is, in a number, rather than leaving it as an intuition — and to note that at some flap counts it is free.

The generalisation #

The useful statement is about constrained optimisation rather than about origami, and it is one that gets forgotten regularly.

A constraint does two things at once. It removes the best answers that violate it, which can only hurt. And it shrinks the space that has to be searched, which can only help a search of fixed effort. The net effect is a race between the two, and which wins is decided by whether the unconstrained optimum satisfied the constraint anyway.

So imposing a symmetry is a bet: it pays exactly when the answer was going to be symmetric, and the search cannot know that in advance. What the census here adds is the shape of the bet in one concrete problem — the payoff alternates with the flap count, the losses are up to fifteen per cent and the gains are a fraction of one, and there is no pattern in the alternation that a designer could use.

The asymmetry of the payoff is worth noticing. A search that guesses right gains almost nothing, because a smaller space of the same shape is not much easier; a search that guesses wrong loses a lot, because the optimum has been excluded. A symmetry constraint is a poor bet on those odds, and the reason to impose one is usually not efficiency at all — it is that a symmetric model is easier to fold, easier to draw and easier to explain.

Who found it, and when #

Circle packing as a design method is Lang’s and Meguro’s, and symmetric packings appear throughout the practice for the reasons above — a flap costs a circle however the circles are arranged: an animal with a left and a right is easier to design symmetrically. The optimisation literature on packing equal discs in a square is separate and old, and the small-n optima have been known and proved for decades.

What is not in either literature is the comparison at equal effort, and the reason is that the two communities are asking different questions. A packing theorist wants the optimum and does not care how long a heuristic takes; a designer wants a model and does not run a free search to compare against. The number that falls out of asking both at once — that the constraint pays at five and eight and costs fifteen per cent at two — is not a number either of them needs.

A count where the constraint forbids the answer #

Two discs is worth one more paragraph, because it is the cleanest instance of the whole mechanism and it can be checked by hand.

The best packing of two equal discs in a unit square puts their centres at opposite corners of the square’s own diagonal, giving a radius of about 0.2929. That arrangement is symmetric under a half-turn about the centre and under a mirror in the diagonal, and it is not symmetric under a mirror in the vertical centre line.

So the vertical mirror forbids it outright. The best two-disc packing that is its own reflection in a vertical line puts both discs on that line, one above the other, at a radius of exactly 0.25 — which is 14.6 per cent worse, exactly the number in the table.

That is the whole result in a case with no search in it at all: the constraint did not make the problem harder to solve, it changed which problem was being solved, and the cost is the distance between two answers rather than between two efforts.

Where the ladder goes next #

The next rung is the same census with unequal discs, which is the case a real design presents. The optima are unknown there, so the comparison would be between two searches with nothing to anchor them — which is a weaker experiment and the only one available, and it is the one that describes what a designer actually does.

There is also a cheap extension worth running: the same census for the three groups at counts beyond eleven, where the free search’s own shortfall grows and the constrained search’s advantage should therefore grow with it. If the gains stay at a tenth of a per cent while the free search gets worse, the “smaller space” explanation is wrong and something else is going on.

The other direction is to ask what the symmetric optimum is for. A symmetric packing produces a symmetric crease pattern, and a symmetric crease pattern folds into a model whose two halves are the same object — which is a property worth paying ten per cent for in a great many cases, and the argument for it has nothing to do with efficiency.