Getting close instead of getting it right

Every base designed by the tree method rests on a circle packing, and every circle packing rests on an optimisation nobody can solve. Packing is the hard part said so and stopped there. This rung asks the question that follows: how far short does a packing that is merely good fall?

It is answerable, for the handful of cases where somebody has proved what the best packing is.

The two numbers, and why they come from different places #

The left column is this collection’s own. The packing routine runs simulated annealing from a grid start and from a hundred and twenty seeded random restarts, and keeps the best radius it saw. It is deterministic — the same call gives the same packing every build — and it knows nothing about what the answer should be.

The right column is not. It is the set of radii that have been proved optimal, which exists only for small n and was established case by case over decades, several cases with computer assistance. For n = 2, 4, 5 and 9 there are exact expressions; the others are numerical values from proofs.

Keeping the two apart is the whole methodological point. A search calibrated against known answers is a search that has been told the answer, and its agreement means nothing. A search that has never seen the yardstick and lands within 0.19% of it has said something about itself.

There is a test in that arrangement which could fail, and it is armed. If the search ever returns a radius larger than a published optimum, the figure throws rather than drawing, because that would mean either the search is buggy or the published number is wrong, and a figure is the wrong place to adjudicate.

What “close” is worth #

The shortfalls are small: 0.004% at two discs, 0.19% at eight, exact at four and nine. It is tempting to conclude that the optimisation is effectively solved for practical purposes, and that conclusion needs two qualifications, one mild and one severe.

The mild one: 0.19% of a radius is 0.4% of an area, and a base’s flap length is proportional to the radius. For a designer, a fifth of a percent shorter flap is nothing. The search is good enough.

The severe one: the search does not know it is close. It returns a radius and no bound. For n = 2 through 9 the shortfall can be stated because somebody proved the optimum; for n = 10 and beyond there is nothing to compare against, and the same search returns the same kind of number with no way to tell whether it is within a fifth of a percent or a factor of two.

That is the situation for every packing an actual design uses. Real bases need ten, twenty, forty discs, of unequal radii, with rivers between them — a considerably harder problem than equal discs in a square — and the published optima run out long before that.

Three things an optimiser can return #

It is worth separating what an optimisation could deliver, because the differences decide what a design can claim.

An optimum with a proof. The answer and a certificate that nothing beats it. This is what exists for equal discs in a square up to about thirty, obtained with great effort.

A solution with a bound. Not the optimum, but a guarantee — within 5% of it, say. Approximation algorithms deliver this, and for many geometric problems they exist. For circle packing in a square there is no useful approximation guarantee in the literature that this essay is aware of.

A solution with nothing. A number produced by a heuristic. This is what bestPacking returns, what most design software returns, and what every packing on this site is.

The third is the normal case in origami design and it is worth being blunt about it, because design papers rarely are. A crease pattern derived from a packing is a valid crease pattern — the packing is the certificate that the flaps do not overlap, and that certificate is exact — but the efficiency claim attached to it is a claim about a search.

The two cases the search gets exactly right #

Four discs and nine discs come out exact, and the coincidence is not a coincidence — it is the one structural fact this figure contains.

Four discs pack optimally in a two-by-two grid, radius exactly a quarter. Nine pack optimally in a three-by-three grid, radius exactly a sixth. Both are perfect squares, and for a perfect square the grid is the optimum, which is the only family where the answer is obvious.

The search finds them because the grid is one of its starting points, deliberately. Without that start the optimiser returned packings a reader could beat by eye at nine discs, which is a poor advertisement for a figure whose subject is that the optimum is hard to find — so the grid was added as a seed and the improvement was immediate.

That is worth flagging as a methodological wrinkle rather than hiding. A search seeded with the answer to some instances is a search that will look better on those instances. The four and the nine are exact because the search was handed them; the two, three, five, six, seven and eight are the honest measurements, and their worst shortfall is 0.19%.

A bound is available, and it is free #

The severe qualification above — that the search returns a radius and no bound — is not quite the end of it. A bound exists for every $n$, it needs no proof of anybody’s, and it is one line of arithmetic.

The densest packing of equal discs in the whole plane is the hexagonal one, at $\pi/(2\sqrt3) = 0.9069$. No packing inside a square can beat that, since a square is part of the plane. So $n\pi r^{2} \le 0.9069$, giving

$$r \;\le\; \frac{0.5373}{\sqrt{n}}$$

for every $n$, always. At nine discs that is 0.179 against a true optimum of one sixth; at four it is 0.269 against a quarter; at eight it is 0.190 against 0.180.

So the search does know something about how close it is. It returns a radius, the bound is computable, and the ratio between them is a certificate: at eight discs it says within 5.4 per cent of optimal, with no proof required and nothing quoted from the literature.

Which is loose by a factor of thirty #

The certificate is honest and it is not tight, and the size of the gap is the useful part.

At eight discs the search’s true shortfall is 0.19 per cent and the certificate says 5.4. The bound is therefore about thirty times looser than the reality — because the hexagonal density is a statement about the infinite plane and a square wastes a strip of width $r$ all the way round its edge, which at these sizes is most of it.

That gap narrows as $n$ grows, since the wasted strip is a perimeter effect and falls as $1/\sqrt{n}$. So the certificate is worst exactly where the proved optima exist and best exactly where they do not, which is a happier arrangement than it sounds: for the ten-, twenty- and forty-disc packings a real design uses, the free bound is the tightest it ever gets and there is nothing else.

The honest position is therefore two grades better than the essay’s third category. A packing search here returns a radius with a computable certificate that is loose but finite, rather than a number with nothing at all — and a designer who wants to know whether to keep searching has a stopping rule that costs one square root.

Why proving an optimum is so much harder than finding one #

The asymmetry is worth understanding, because it is the same asymmetry that runs through this whole field.

Finding a good packing is a search over configurations, and a search can stop when it stops improving. Proving a packing optimal means ruling out every other configuration, and the configurations form a continuum. There is no finite list to exhaust.

The proofs that exist work by discretising that continuum: divide the space of configurations into finitely many regions, bound the best achievable in each, and show all but one region is worse. That is why several of them are computer-assisted and why the effort grows so quickly with n — the number of regions explodes, and each one needs its own bound.

This is the same shape as everything else in this field. A crease pattern that folds comes with a certificate and one that does not requires an exhaustive argument. A packing that exists is exhibited; a packing that is best has to be argued against everything. Positive claims are cheap and negative claims are expensive, all the way down.

What a designer actually needs #

The optimisation framing is standard and it is not quite the designer’s question, which is worth saying because it changes what “close enough” means.

A designer has a subject, a sheet and a target proportion. What they need is a packing whose flaps are long enough for the model, whose crease pattern is foldable, and whose waste is tolerable. That is a satisficing problem with a threshold rather than an optimisation, and thresholds are much easier: a search that returns something above the line has answered the question completely.

Where the optimisation framing does bite is at the margin, and the margin is where interesting design happens. A model that needs one more flap than the sheet comfortably holds is a model where the difference between a good packing and the best one decides whether it exists. That is exactly the regime where nobody knows the best one.

A base is not graded on its packing alone #

There is a second reason the optimisation framing understates the difficulty, and it concerns what happens after the packing is chosen.

Two packings of equal efficiency can produce bases of very different character — one with its flaps conveniently grouped and one with them scattered, one whose crease pattern lands on a grid and one whose angles are arbitrary. A designer choosing between them is optimising something no formula captures, and the packing efficiency is a constraint they are working within rather than the objective.

This is the ordinary situation whenever an engineering problem is handed to an optimiser: the thing that can be measured becomes the objective, and the things that cannot get called taste. Naming that is not an argument against measuring, and how much paper is wasted is worth measuring. It is an argument against reading a percentage as a verdict.

What is measured and what is not #

Three statements, in decreasing order of how firmly they are established here.

Measured: for two through nine equal discs in a square, the search here falls short of the proved optimum by between nothing and 0.19%, and never exceeds it. Reproducible — the seeds are fixed and the same call returns the same packing on every build.

Quoted: the proved optima themselves. They are somebody else’s work, and their role here is to be a yardstick the search can fail against.

Not established: anything about larger n, unequal discs, rivers, or the packings that real designs use. The search behaves well on the cases where its behaviour can be checked, and extrapolating from that is exactly the reasoning that a worst-case result is a warning about.

What the figure cannot show #

The figure compares radii and says nothing about arrangements. Two packings with almost the same radius can put their discs in completely different places, and for a designer the placement is what determines the crease pattern — the ridges and hinges come from which discs touch, so two packings of equal quality can yield patterns of very different complexity.

It also shows only the cases with a published optimum, which are the small ones, which are the easy ones. The search is being graded on the part of the exam where the answers are known, and that is a selection effect rather than a sample.

And the shortfall is reported as a fraction of the radius, which is the natural unit for a flap length and not the natural unit for anything else. In area it doubles; in the number of flaps that fit on a sheet it does something else again. A single percentage hides that choice, and the choice is stated here rather than left in the arithmetic.

The idealisation, named #

Equal discs in a square is the model problem and it is not the design problem, in three specific ways.

Discs are unequal. A flap’s disc has the radius of that flap’s length, and a model with a long neck and short legs has discs of wildly different sizes. Packing unequal discs is a harder problem with fewer proved cases.

There are rivers. The paper joining two flaps needs its own width, which turns the packing into one of discs and strips together, and takes it outside the classical problem entirely.

The container is not always a square. A rectangle, and sometimes a shape chosen to suit the model. The proved optima are for squares.

So the numbers here bound the quality of a search on a problem that is a simplification of the one that matters. That is a legitimate way to test a search and it is not a claim about design, and the difference between those two is where a figure like this most easily misleads.

The decision version, which is where the hardness lives #

There is a translation between this essay’s optimisation and the decision problems of the rest of the field, and making it explicit ties the ladder together.

Every optimisation has a decision version: instead of what is the largest radius, ask is there a packing with radius at least r? The two are equivalent up to a search over r, so anything hard about one is hard about the other, and the decision version is the one complexity theory is set up to talk about.

Posed that way, packing joins the rest of the subject. It is a question with a short certificate when the answer is yes — here are the centres, check the distances — and no short certificate when the answer is no, because “no arrangement achieves r” is a statement about a continuum. That is precisely the asymmetry that makes flat-foldability’s decision problem what it is, and it is why the proved optima took decades while good packings took an afternoon.

So the design side and the folding side of this subject have the same difficulty in the same place, arrived at from opposite directions. One asks whether a stacking exists and finds that exhibiting one is easy and ruling all of them out is not. The other asks whether a packing exists and finds exactly the same thing.

Who proved these, and when #

Optimal packings of equal circles in a square have been established one n at a time since the 1960s. The small cases are classical; larger ones came from work by Ronald Graham, Boris Lubachevsky and others through the 1990s, with several cases settled by computer-assisted proof. The numerical records for n beyond the proved range are maintained as an ongoing collection and are records rather than results.

The general problem is hard in the formal sense, which is what the earlier rung of this ladder said. The relevant point here is narrower and more useful: the hardness is in the proof, not in getting a good answer, and a subject can be practically comfortable and theoretically open at the same time.

Where the ladder goes next #

This rung scored an optimisation against a yardstick that somebody else had to prove. The counting side of the subject has no yardstick at all — the map-folding table is nine numbers and a wall, every one of them from exhaustive search, with nothing to check them against but each other and one set of values computed in 1971.

Between them those two rungs are the field’s two honest positions. Where an answer can be verified cheaply, a search is enough and its quality can be measured. Where it cannot, the only method is exhaustion, and the subject knows exactly as much as somebody has been willing to compute.