Spelling a tree on a grid

Box pleating gives up the efficiency of a free packing and buys creases that land where they are supposed to, which for a design with hundreds of folds is not a compromise but the only thing that makes it foldable. The bargain has been priced on this site once already, in paper: a lattice packing of six flaps reaches 0.1398 against a free search’s 0.1876, and the lattice’s optimum is knowable where the free one is not.

That is the price in size. There is a second price, and it is the one a designer actually notices.

The two prices are easy to run together and they are quite different. The price in size is paid once and can be quoted: a lattice packing is a known amount worse than a free one, and a designer who accepts it gets a foldable pattern in exchange. The price in shape is paid on every limb, it is not quoted anywhere, and — as the measurement below shows — most of it is avoidable.

The grid rounds the shape #

A grid does not merely make a design coarser. It makes the ratios between the limbs into ratios of whole numbers.

A subject with limbs 1, 1.37, 2.15 and 1.62 is a subject whose second limb is 1.37 times its first. On a grid of twelve, that limb has to be some whole number of squares and so does the first, and 1.37 has to become a ratio like 8 : 6 or 11 : 8. The design’s proportions are no longer the designer’s; they are whatever the nearest available fraction is.

That matters because a model’s proportions are most of what makes it look like what it is. Getting a leg five per cent long is visible. Getting the ratio of a leg to a neck five per cent wrong is more visible still, because a viewer compares parts to one another and not to a ruler.

Rounding each limb is not rounding the design #

Here is the measurement, and it is the essay.

Scale the subject so that its longest limb is exactly g squares, and round every other limb to its own nearest whole number. That is the obvious procedure and it is what anybody does. Measure how wrong the worst limb ends up, as a fraction of what it should have been.

Then search every vector of whole numbers up to g and find the one whose worst limb is least wrong. The search is exhaustive rather than clever, which is the point: the comparison is against the obvious answer, and a complete search settles the difference beyond argument.

At four squares they agree, and at six they agree. At eight the per-limb rounding gives 4 : 5 : 8 : 6 and a worst error of 7.2 per cent; the best available is 3 : 4 : 6 : 5, worst error 6.0 per cent, on a grid three units coarser than the one that was asked for. At twelve: 6 : 8 : 12 : 9 at 5.9 per cent against 5 : 7 : 11 : 8 at 2.4 per cent. At sixteen: 7 : 10 : 16 : 12 at 4.9 per cent against — 5 : 7 : 11 : 8 again, still 2.4 per cent, because nothing between twelve and sixteen improves on it. At twenty-four: 1.3 per cent against 0.78.

It is worth reading the twelve-unit line slowly, because it is the clearest. The obvious answer uses the longest limb as the anchor and puts it at twelve; everything else rounds to what it rounds to; the worst limb comes out 5.9 per cent from where the designer wanted it. The best answer puts the longest limb at eleven — accepting an error on the limb everybody would have got exactly right — and every other limb then lands closer, and the worst error more than halves.

That is a general shape and not a coincidence: insisting that one limb be exact is a constraint, and constraints cost. The limb a designer instinctively anchors on is usually the longest, and the longest is the one whose exactness is worth least.

The two things going wrong #

The per-limb rounding fails for two reasons and they are worth separating.

The first is that the errors interact. What matters is the worst ratio, and a ratio has two limbs in it. Rounding one limb up and its neighbour down doubles the damage to the ratio between them, and rounding each to its own nearest has no way of noticing.

The second is that the scale is a free variable and the rounding fixes it. Setting the longest limb to g squares is one choice among many; a slightly different scale puts every limb near a different whole number, and the best scale is not the one that makes any particular limb exact. The exhaustive search is effectively searching over scales as well as over roundings, which is why it can return a coarser answer.

That second point explains the non-monotonicity. Going from a six-grid to an eight-grid makes the per-limb rounding worse, from 6.0 per cent to 7.2, which is impossible for a procedure that is really rounding numbers and entirely possible for one that has silently fixed a scale.

There is a third thing, smaller and worth noting because it explains the flat stretch in the graph. The best whole-number version at twelve is also the best at thirteen, fourteen, fifteen and sixteen — the search is allowed finer numbers and does not want them. A set of small whole numbers that happens to sit close to the target ratios is hard to beat, and beating it requires going far enough that a genuinely better set of large numbers appears.

That is the same phenomenon a folder meets when reaching a fraction by folding: the cheap constructions reach some fractions and not others, and the reach is not a smooth function of effort.

The best-error curve cannot rise #

The two lines in the graph behave differently, and the difference is structural rather than empirical — which is worth stating, because it tells a reader which of them to trust.

The search at a grid of g tries every whole-number vector with entries up to g, and every vector available at a coarser grid is among them. So the best error is non-increasing in g by construction: a finer grid can never do worse, because it can always decline to use the extra room. The flat stretch from twelve to sixteen is that fact in its mildest form — the search was offered four more units and took none of them.

That makes the solid line a frontier rather than a measurement. It is the best that any procedure could do at that resolution, and every method a designer might invent lies somewhere above it.

The dashed line has no such guarantee and is not entitled to one. Per-limb rounding fixes the scale before it rounds anything, so a finer grid hands it a different scale rather than a superset of choices, and nothing stops the new scale being worse. That is why it rises between six and eight, and it could rise anywhere.

It is also the assertion the measurement is guarded by. The search’s best error is required to be non-increasing across the whole sweep of grids, and a run in which it rose at any resolution would be a broken search rather than a finding — a vector missed, or the objective computed differently at two resolutions. It has never risen.

How fast the frontier ought to fall #

The section above declines to be about approximating real numbers by whole ones, and it is right to: that subject is old and deep and nothing measured here adds to it. It does, however, predict how fast the solid line should fall, and checking one against the other is worth a paragraph.

Approximating k ratios at once, with a common denominator no larger than N, can always be done to within about $N^{-(1+1/k)}$. The bound is Dirichlet’s, it is more than a century old, and it is a guarantee rather than a typical case. A four-limb subject has three ratios to hit, so $k$ is three, the exponent is 4/3, and doubling the grid should cut the best achievable error to a little under two fifths of what it was.

Measured: from eight units to sixteen the best error falls from 6.0 per cent to 2.4, a ratio of 0.40 against a predicted 0.397. From twelve to twenty-four it falls from 2.4 to 0.78, a ratio of 0.33 — better than the bound, which is allowed, because the bound is a worst case over every possible set of ratios and this is one particular animal.

Two things follow. The frontier’s erratic appearance is a small-numbers effect on a curve that is smooth in the aggregate: the steps are where a good vector happens to become available, and the trend running through them is the exponent. And the return on a finer grid is diminishing for a reason that has nothing to do with folding at all. A designer who doubles the grid is buying a factor of two and a half in accuracy for four times as many squares to fold, and that trade gets worse with every limb the subject has — more limbs is a larger $k$, an exponent nearer to one, and a doubling that buys barely a halving.

Coarser is better, and what that is worth #

The most useful consequence is the one that sounds wrong: at a given resolution the best whole-number version of a design often uses fewer squares than the obvious one.

5 : 7 : 11 : 8 totals thirty-one units. 6 : 8 : 12 : 9 totals thirty-five. The first is a better likeness of the subject and it is a smaller design — fewer creases, less paper spent on the grid, a base that can be folded from a smaller sheet at the same crease pitch.

That inverts the usual advice. A box pleater who wants a better likeness is told to use a finer grid, and a finer grid is more work at every stage. What the search says is that the gain from a finer grid is erratic — sixteen is no better than twelve on this subject — and that the gain from choosing the whole numbers properly is available at any resolution, for nothing.

There is a cost to the coarser answer and it should be stated. A design at 5 : 7 : 11 : 8 has less resolution to spend on shaping — the part of a design that happens after the base, where a designer narrows a flap or puts a fold in a leg — and shaping is exactly what fine grids are for. So the recommendation is not “use a coarser grid”; it is “choose the whole numbers before choosing the grid”, which is a different and cheaper instruction.

What the search is and is not #

The comparison is between two procedures and both of them are honest, so it is worth being clear about which is being criticised.

The exhaustive search cannot be worse than the per-limb rounding, because the per-limb rounding’s vector is one of the ones it tries. That is the assertion the measurement is guarded by, and it is stated in the strict direction: if the search ever came back worse, the search would be broken.

What the search is not is a proposal for how design software should work. Enumerating every vector of whole numbers is affordable for four limbs and a twenty-four grid and is not affordable for a subject with thirty limbs. How one would do it properly, and what that would cost, is a question about algorithms and belongs to a different subject; nothing here is a claim about it.

Nor is any of it a theorem about approximating real numbers by whole ones. That is number theory, it is old and deep, and what is reported above is a measurement on the trees an origami designer would actually draw.

How a designer would use it #

The instruction that falls out is short and does not require any of the machinery above.

Before fixing a grid, write the subject’s limbs as a list of ratios. Then try the small whole-number vectors — everything up to eight or ten units, which is a few hundred combinations and can be done on paper — and see how close each gets. If one of them is close enough, that is the design, and the grid follows from it rather than the other way about.

What that avoids is the failure mode the graph shows: a designer choosing a fine grid because fine sounds accurate, anchoring on the longest limb because it is the obvious anchor, and arriving at proportions further from the subject than a coarser grid would have given — with more creases to fold as the reward.

Where the model stops #

One subject, four limbs. The numbers quoted are for one set of proportions. Another set would give different crossings and possibly no disagreement at all — a subject whose limbs are already in simple ratios is spelled exactly at some resolution and there is nothing to choose.

The worst limb is the objective. Minimising the largest relative error is one choice; minimising the total, or weighting the limbs by how visible they are, would give different answers. The objective is stated rather than derived, and a designer’s real objective is about how the model looks.

The tree condition is not checked. A vector of whole-number limbs still has to admit a packing, and the separation condition through the tree is a further demand the rounding might break. Nothing above verifies that the best whole-number tree is packable.

No crease pattern is built. The measurement is on limb lengths, which are the input to the packing rather than the output. What the rounding does to the finished pattern is a step further on.

Why box pleating tolerates it #

The obvious objection is that box pleaters have been doing this for forty years without noticing a problem, so how bad can it be.

The answer is that the practice has absorbed it in two ways. Designers pick subjects and proportions that suit the grid, adjusting the animal to fit the arithmetic rather than the other way round — which is a real design decision made for a reason nobody states. And grids in serious box-pleated work are fine: thirty-two, sixty-four, a hundred and twenty-eight squares across, at which resolution the per-limb rounding’s error is small in absolute terms even when it is twice what it needed to be.

Both of those are accommodations rather than solutions, and both are expensive in their own way — the first in what can be designed, the second in how many creases have to be folded. The measurement says the accommodation is not necessary at the resolutions where it costs most.

There is a neat historical rhyme here. Folding reaches every fraction exactly and reached them long before anybody worked out how, and the practice meanwhile got by with a method that converges without arriving. Practices absorb arithmetic they have not been given, and they absorb it by narrowing what they attempt.

Where the ladder goes next #

The obvious continuation is the one the model-stops section names: does the best whole-number tree pack? A rounding that produces a better likeness and an unpackable tree is not a better design, and joining the two searches is a single step that has not been taken here.

The other direction is the grid itself. Every resolution above is a power-of-two-ish subdivision because that is what folding produces cheaply, and the ladder that reaches any fraction exactly means a folder is not restricted to those. A grid of eleven is as foldable as a grid of twelve and is never used, and the measurement above suggests it might sometimes be the better one.