How much paper is wasted

Every design wastes paper. The flaps claim discs, the discs do not tile the plane, and whatever is left over becomes structure rather than length. The natural question is how much is left over at best, and the natural expectation is that somebody worked this out long ago.

Nobody did. For all but the smallest numbers of flaps the best possible packing is unknown, and the values quoted in the design literature are the best anybody has found.

What efficiency means here #

The word gets used loosely, so it is worth pinning down which quantity is meant.

The efficiency of a packing is the fraction of the square’s area covered by the discs. Nothing else: not how good the resulting model looks, not how easy it is to fold, not how well the leftover paper is shaped.

That definition is useful because it is the quantity the design method actually trades against. A flap’s length is its disc’s radius, so a packing with higher efficiency gets longer flaps out of the same sheet, and a design that needs longer flaps needs a better packing or a bigger sheet.

It is also narrower than it sounds. Two packings with the same efficiency can produce very different bases, because efficiency says nothing about how the leftover paper is distributed. A packing with all its slack in one corner and one with slack spread thinly everywhere score the same and fold quite differently.

What a search finds #

The bars above come from an optimiser rather than from a table, and the method matters because it determines how much to believe them.

For each number of discs, the generator starts from a grid arrangement and from a hundred and twenty random ones, and repeatedly nudges a single disc, keeping any move that does not make the common radius smaller. The step size shrinks as the run proceeds. The randomness is seeded, so the same packing comes out every time and the figure is reproducible.

What it finds matches the best packings in the literature to within a fraction of a percent for every count up to nine. That agreement is reassuring and it is not a proof. The search could be stuck in the same local optimum the literature is stuck in, and for the counts where the literature’s value has been proved optimal — which is a short list — the agreement means the search found the answer rather than that the search is trustworthy in general.

The honest label for each bar is therefore “the best found”, and that is what the figure says. A stronger claim would require a proof, and for most of these counts no proof exists.

The numbers are not monotone #

The most instructive feature of the results is that they go up and down.

Four discs fill 78.5% of the square. Five fill 67.3%, which is worse. Six is worse again at 66.3%, seven is 66.9%, eight is 72.8%, and nine returns to 78.5%.

Four and nine are the square numbers, and their optimal packings are grids: two by two and three by three, each disc in its own cell, touching its neighbours and the walls. A grid uses the square perfectly because the square is what it was built for, and the efficiency is π/4 exactly.

Five, six and seven have no grid available. Their best packings are irregular, with discs in slightly awkward positions and gaps that cannot be closed, and they lose ten percentage points for it.

So efficiency is not a smooth function of how many flaps a design needs. It is a jagged one, with peaks at the counts that happen to fit the boundary, and a designer who needs six flaps is paying for the arithmetic of the number six.

Where the wasted paper goes #

Calling the leftover “waste” is a convenience and it is worth undoing, because the leftover is not thrown away.

Every point of the sheet not inside a disc still ends up somewhere in the folded model. It becomes the surfaces between the flaps: the body an insect’s legs come out of, the membrane between a wing and a thorax, the layers that make a base thick. None of it is discarded, because nothing is ever cut.

So a low-efficiency packing does not produce a smaller model. It produces a model with shorter flaps and more body, and whether that is worse depends entirely on the subject. A beetle wants a large body and short legs; a spider wants the opposite. Efficiency measures how much of the sheet became length, and length is only one of the things a design needs.

The word is still worth keeping, because for the subjects that motivated the method — insects, with many long thin appendages — length is exactly the scarce resource. The vocabulary comes from that case and quietly assumes it.

The bound nothing reaches #

There is one number in this area that is proved, and it is worth knowing what it does and does not say.

The densest packing of equal discs in the infinite plane is the hexagonal one, in which every disc touches six others, and its density is π/√12 — a little over 90.69%. That this is optimal was conjectured by Kepler’s contemporaries, argued by Thue, and proved rigorously by Fejes Tóth in 1940.

No packing inside a square reaches it. The reason is the boundary: a disc against a wall touches at most four others rather than six, so the outer ring of any packing is less dense than the interior, and the outer ring never becomes negligible at the counts a design actually uses.

The loss falls slowly. For large n the shortfall from the hexagonal density scales like one over the square root of n, which means a packing needs hundreds of discs before it looks like the infinite case. Origami designs have between four and thirty, which is exactly the regime where the boundary dominates.

So the 90.69% is a ceiling that tells a designer very little. The relevant question is what the best packing of this number of discs in this square is, and the ceiling does not answer it.

The bound that does apply is π/4 #

The hexagonal ceiling is unreachable at these counts, and there is a second value that is reachable, exactly, and that the essay’s own numbers are already sitting on.

A $k \times k$ grid of discs in a unit square gives each a radius of $1/(2k)$, so the area covered is $k^2 \cdot \pi/(4k^2) = \pi/4$ — independent of $k$. Four discs and nine discs do not merely both do well; they do identically well, at 78.54%, and the same value is available at sixteen, twenty-five and thirty-six.

So the jagged plot has a flat top. Its peaks are not a run of good luck at particular counts; they are one number, attained whenever the count is a perfect square, and no arrangement inside a square has ever beaten it at any count a design uses.

Which puts the whole plot in a twelve-point band #

That changes what the variation means. The best found runs from 66.3% at six discs to 78.5% at four and nine — a band twelve points wide, entirely below π/4 and entirely above the hexagonal ceiling’s reach.

In the currency a designer feels, twelve points of efficiency is $\sqrt{66.3/78.5} = 0.919$: eight per cent of flap length between the best count and the worst.

That is the honest size of the arithmetic-of-six penalty, and it is smaller than the percentages suggest. It also gives the one piece of advice this measurement supports: a subject that can be reduced to four, nine or sixteen appendages is packing against a value that is exactly known and exactly attainable, and every other count is being fitted to a boundary by a search whose answer nobody can certify.

Which theorem was checked, and how #

Two things are verified rather than asserted.

The radius reported for each packing is measured off the arrangement rather than claimed: it is the largest value that keeps every disc inside the square and no two overlapping, computed as a minimum over the wall clearances and half the pairwise separations. A packing whose discs overlapped would report a smaller radius rather than a false one.

The generator also asserts that no packing exceeds the hexagonal density, and throws if one does. That check has never fired and is not expected to; it is there because a search that reported an impossible density would otherwise report it quietly, and an assertion that never fires is only worth having if the thing it forbids is genuinely forbidden.

What cannot be checked is optimality. The figure does not claim it, and there is no computation the generator could run that would establish it — proving a packing optimal is a case-analysis argument, done by hand or by exhaustive computer search over configurations, and it has been carried out for a handful of small counts only.

Where the model stops #

Equal discs. A real design has flaps of different lengths, so its discs have different radii, and unequal-disc packing is harder still. The equal case is the one with published optima to compare against.

No rivers. An internal edge of the skeleton costs a strip rather than a disc, and a packing with rivers is a different problem again — the leftover is not the leftover between circles.

Nothing about foldability. A record packing yields a crease pattern whose layer ordering may be awkward or impossible to achieve by hand, and efficiency does not see that at all.

Square sheets. Everything above is about packing into a square. Rectangles, and in particular the A-series proportions, give different answers, and a designer who is allowed to choose the paper shape has a degree of freedom this analysis ignores.

Efficiency is not quality. Higher efficiency means longer flaps and thinner leftovers. Thin leftovers mean more layers in less paper, which is harder to fold and thicker at the core. Past a point, a more efficient packing produces a worse model.

Rivers change the question. The general packing condition is about distances through a tree, and an efficiency computed from discs alone ignores whatever the internal edges are claiming.

Uniaxial bases only. As everywhere in this theory, the whole apparatus assumes a base whose flaps lie along one axis.

The search is a search. Every number in these figures could be beaten. That is the honest state of the problem and the figures say so.

The surprise: the theory has a hole where it looks solid #

Circle packing is presented in the design literature as the rigorous part of the subject — the place where art gave way to mathematics, with a theorem and a program to back it up. That description is accurate about the condition and misleading about the optimum.

The condition is a theorem: a packing satisfying it yields a base, and one violating it does not. That part is settled.

The optimisation is not settled at all. Given a tree, find the packing that maximises the scale — which is what a designer wants — and there is no known efficient algorithm and no proof of optimality for the solutions found. TreeMaker uses nonlinear optimisation and reports what it converges to.

So the rigorous-looking half of origami design contains, at its centre, an optimisation problem in the same state as most packing problems: easy to state, easy to attack heuristically, and open. That is not a defect of the field. It is what happens when a practical subject is honest about which of its questions have been answered.

What a designer does instead #

The gap between the theory and the practice is filled by a habit worth describing, because it is not a compromise so much as a different objective.

A designer rarely maximises efficiency. What gets maximised is the flap lengths that matter — the ones that become the legs and the wings — with the rest allowed to be shorter than optimal. That is a weighted problem rather than the uniform one, and its solutions look nothing like the record packings.

The second thing that happens is that the packing gets snapped to a grid. Box pleating gives up perhaps ten to twenty percent of efficiency and buys creases that land where they are supposed to, which for a design with several hundred folds is not a trade at all. The best packing in the world is worthless if the folder cannot hit the reference points.

So the efficiency numbers in this essay describe an idealised problem that nobody solves. They are still worth having, because they say what the ceiling is and therefore how much the grid actually costs.

Measuring a real design #

The natural next question is what efficiency actual published designs achieve, and the answer is harder to get than it looks.

A published crease pattern does not come with its packing. Recovering the discs means identifying which vertices are flap tips, measuring the radii, and reconstructing the skeleton — a reverse-engineering exercise that is routine for a simple base and genuinely difficult for a complex one. Nobody appears to have done it systematically across a corpus.

What can be said is that the numbers quoted informally by designers sit well below the record packings: figures in the region of forty to sixty percent are typical for complex work, against the sixty-five to seventy-nine percent the equal-disc records reach. Some of that gap is unequal radii, some is rivers, and some is the grid.

The absence of a measurement is itself worth noticing. This is a field with a design algorithm, a program that implements it, and thirty years of published patterns, and the most basic question about how well the method does in practice has no published answer. That is not unusual in a subject whose practitioners are makers rather than analysts, and it is the kind of gap that a couple of afternoons with a corpus and a script would close.

Who found it, and when #

Disc packing in a square has been studied since the 1960s and its history belongs to discrete geometry rather than to folding.

Michael Goldberg published packings for small n in 1970, and the sequence of best-known values has been improved incrementally since, largely by computer search — Boris Lubachevsky and Ronald Graham’s work in the 1990s produced many of the records still standing. Optimality is proved only for n up to about thirty, and each proof is its own piece of work.

The origami connection came from the other direction and much later, when Meguro and Lang independently identified the disc as what a flap costs. The design community inherited a packing problem whose literature already existed and had not been written with them in mind.

The inheritance is imperfect, and the imperfection is instructive: the published records are for equal discs in a square, and a designer needs unequal discs and rivers in whatever paper is to hand. So the numbers that are rigorous are not quite the numbers that are wanted, which is a common fate for a borrowed result.

What an open problem looks like from inside #

It is worth being explicit about the epistemic position, because “open problem” covers several quite different situations.

This is not an open problem in the sense of a conjecture nobody can prove. It is open in the weaker and commoner sense: the answers for small cases are known and proved, the answers for medium cases are believed and unproved, and there is no general method. Somebody with a good optimiser can improve a record; nobody expects a formula.

For a designer that distinction matters less than it might. The practical question is whether a given packing can be improved, and the practical answer is to run a search and see. A proof of optimality would change nothing about the workflow.

For the subject it matters more. A field that describes itself as having turned an art into an algorithm should be clear that the algorithm has a heuristic at its centre, and that the heuristic is the part everybody depends on. The condition is a theorem; the optimisation is a search; and the two get quoted together as though they had the same standing.

The ladder from here #

Later rungs against this anchor: unequal-disc packing, and what is known about it. The proofs of optimality for small n, which are case analyses worth seeing once. Packing with rivers, where even the statement of the optimisation is fiddly. The scale-optimisation problem TreeMaker actually solves, and what its objective function is. Efficiency of published designs, measured rather than estimated. And the question of what proportion of paper a good design wastes, which is a different quantity from the one here and has never been measured systematically.

The efficiency question sounds like bookkeeping and turns out to be the open problem at the centre of the one part of this subject that has an algorithm.