Two packings, one radius

A flap costs a circle, and once a subject has been turned into a set of circles, designing the model is fitting them into the square. That step is where the difficulty of origami design now lives, and what a search for it reports is a radius: the largest the discs can be without overlapping.

The radius is the number every table quotes, every comparison uses and every published result is stated as. It is not what a crease pattern is built from.

The step from a packing to a pattern takes the contacts: a ridge crease runs between two discs that touch, a disc touching the sheet’s edge is held there, and the creases are determined by which pairs are in contact rather than by how big the discs are. So the object that decides the design is a graph — and two packings with the same radius need not have the same one.

What the graph is, and why it is the design #

A packing hands a designer three things: the centres, the radius, and — implicitly — the list of pairs that touch.

The third is what the construction uses. Between two touching discs the paper between the flaps has to be accounted for, and the crease that accounts for it runs along the line joining their centres; a disc against the sheet’s edge is pinned by that edge; and the hinge creases that separate one flap’s paper from the next follow from the same list. The radius appears in the construction only as the scale.

That makes the contact graph the combinatorial content of a packing, and the radius its metric content. Two packings can agree on the second and disagree on the first, and when they do they are two designs that a table would record as one result.

The measurement #

The search is run at several restart counts. That is the honest way to get independent answers out of a deterministic optimiser: each run is complete, each would have been reported on its own, and none of them knows about the others.

Runs whose radius differs from the best by more than a ten-thousandth are discarded, so every arrangement compared is one anybody would have accepted as the answer. What is left is sorted by contact graph.

The last column counts the contact graphs among the runs that agree about the radius:

Two of the five counts are greater than one, and three are not. That both happen is what makes the measurement worth anything: a result where every flap count came back with several graphs would be measuring the search’s noise, and one where every count came back with a single graph would be measuring nothing at all.

Provably different, not merely differently drawn #

Two arrangements can look different and be the same graph relabelled, which would make the count above an artefact of how the discs happened to be numbered. The comparison therefore uses a label two isomorphic graphs must share: each disc starts with how many edges of the sheet it is held against, and then repeatedly takes on its own label together with its neighbours’ labels, sorted.

That is a standard invariant and it is used here in the one direction it is sound. Two graphs whose labels differ are certainly different graphs. Two whose labels agree may or may not be, and nothing here claims they are — so the counts above are lower bounds on how many distinct designs the search returned, which is the conservative direction for the argument being made.

What counts as touching #

The uncomfortable part of the measurement is that contact is a judgement.

Two discs a millionth of a unit apart are touching for every purpose a folder has and are not touching arithmetically, so the graph depends on a tolerance. A contact graph that is genuinely a property of the packing would have a plateau — a range of tolerances over which the count of contacts does not move — and the searched packings do not have one.

That is not a defect in the measurement; it is the finding stated a second way. The arrangement is only approximately at the optimum — a stochastic search gets close and stops — so the discs that “should” be touching are a hair apart, and how many of them count depends on where the line is drawn. At the exact optimum, which for most of these counts nobody has proved, the contacts would be exact and the plateau would exist.

So the situation a designer is actually in is worse than the headline. Not only does the radius fail to determine the graph; the graph itself is only defined once somebody has chosen how close counts as close.

Why some flap counts and not others #

The two counts where the graphs differ are the small ones, and the mechanism is the freedom that an earlier rung measured directly: at some numbers of discs the best packing has a disc that is not pinned, and a disc free to wander is a disc whose contacts are not decided.

Seven is the count where that freedom is largest and it is also, here, a count where every run returned the same graph. That is not a contradiction — the free disc at seven wanders inside a region without changing which discs it touches, which is a different kind of freedom from the one at five and six, where the runs settle into arrangements that differ in how many contacts there are at all.

The distinction is worth keeping, and it is the same distinction the molecule that does not exist makes about the step after this one: a packing can be under-determined in its positions with a determined graph, or determined in its positions with the graph in doubt because the positions are only approximate. The first is geometry and the second is arithmetic.

What a designer should record #

The finding is small enough to state as a habit, and stating it that way is more useful than another paragraph about optimisation.

Record the contacts. A packing written down as centres and a radius is a packing somebody has to re-derive the design from, and the re-derivation involves a threshold. Written down as a list of touching pairs plus the centres, it is a design; the radius is then a check rather than the record.

Record the tolerance. Where the packing came from a search, the contacts were read at some closeness and the number of them is a function of it. Six contacts at a thousandth and four at a ten-thousandth are the same arrangement described twice, and only one of the two descriptions is the one the pattern was built from.

Check the efficiency separately. How much paper a design wastes is a function of the radius alone, so two packings with different graphs are indistinguishable by it — the measure everybody compares designs with is exactly the measure that cannot see the difference.

Check for a free disc before believing either. A disc that is not pinned moves without changing the radius, and whether it also changes the contacts is the question that separates the two kinds of under-determination above. The test is cheap: count each disc’s contacts including the sheet’s edges, and anything with fewer than three is free to move.

Between them those three turn a packing from a number into an object, which is what the next step of the design needs it to be.

What pins a disc, exactly #

The habit above proposes a cheap test — count each disc’s contacts, including the sheet’s edges, and treat anything under three as free — and the exact criterion behind it is worth writing out, because it has a sharper version and the sharper version does more work.

A disc in the plane has two degrees of freedom, and each contact forbids motion in one direction: toward whatever it is touching. Two contacts therefore forbid two directions, and that leaves the disc free unless the two forbidden directions are diametrically opposite — otherwise there is always a direction with a positive component away from both, and the disc slides that way. So the condition is not a count but a spanning condition: a disc is pinned when its contact directions positively span the plane, which needs three of them in general and can be done with two only when they are exactly opposed.

Three is therefore the working number and two is a case to check rather than to dismiss. On a searched packing the two-contact case will essentially never be exact anyway, which puts it on the same footing as everything else here.

Which gives the tolerance a floor #

That criterion turns into a count over the whole arrangement, and the count is what the plateau measurement was missing.

Write $e$ for the pairs of discs in contact and $b$ for the disc-against-edge contacts. Every disc needs at least three contacts; each disc-disc contact supplies one to each of two discs and each edge contact supplies one to a single disc. Summing over the discs,

$$2e + b \ge 3n.$$

A contact graph violating that describes an arrangement with a disc free to move, and a disc free to move is a disc that can be moved to make room — so the packing was not at a maximum and the graph is not the graph of an optimal packing.

That is a principled floor for the tolerance. The essay reports that the contact count on a six-disc packing goes one, four, six as the tolerance is loosened through three decades, and that there is no plateau to choose from. There is now a reason to choose: read the graph at the smallest tolerance whose count satisfies the inequality, since anything tighter is describing a packing that could not have been optimal, and anything looser is admitting contacts the arrangement does not support.

It does not manufacture a plateau and it should not be read as doing so. Two tolerances that both satisfy the inequality can still give different graphs, and the inequality is necessary rather than sufficient — an arrangement can satisfy it and still have a particular disc short of contacts while another has a surplus, so the per-disc version of the check is the one to run rather than the total.

What it does supply is the thing the measurement had none of: a criterion internal to the packing rather than a number somebody picked. The tolerance stops being a free parameter and becomes the answer to a question the arrangement itself can be asked.

Which theorem was checked, and how #

The radii are compared before the graphs are. A run whose radius differs by more than a ten-thousandth is not in the comparison at all, so nothing below is a comparison between a good packing and a worse one.

The invariant is used only to separate. Graphs the label distinguishes are different; graphs it does not are counted together. The reported count is therefore never an over-count.

The tolerance is swept rather than chosen. The plateau figure runs over five decades, and the absence of a plateau is reported rather than a single tolerance being picked and defended.

Both outcomes must occur. The assertion behind the figure fails if every flap count returns one graph and fails if every one returns several — either would mean the measurement was about the method rather than about packings.

Where the model stops #

Five counts is five counts. Nothing here estimates how often a radius fails to determine a graph; the measurement is a count over the flap numbers it was run on, with the denominator attached.

The optimum is mostly unproved. For all but a handful of these counts nobody knows the best radius, so “agrees about the best radius” means agrees about the best the search found. That is the right comparison for a designer using a search and is not a statement about optimal packings.

Every flap in the model lies on one axis. The uniaxial restriction is what makes the circle argument true in the first place, and nothing here relaxes it.

Discs are the model, and the model is a simplification. Flaps that hang from different places need rivers rather than circles, and a river’s contacts are a richer object than a pair of touching discs; the argument here is about the simplest case and gets no easier in the general one.

Nothing here computes a crease pattern. The claim is that the graph decides the pattern and that the radius does not decide the graph. Building the two patterns and comparing them is a further step, and it needs the packings to be exact rather than approximate — which is exactly what the plateau measurement says they are not.

What the picture cannot show #

Two packings drawn side by side look like two arrangements of dots, and the thing that differs between them — which pairs are in contact — is visible only as lines somebody has chosen to draw. A reader cannot check the contacts by eye: two discs that touch and two discs a hundredth apart are the same picture at any reasonable size.

Nor can the figures show that the two graphs are not relabellings of one another. That is a computation over every possible relabelling in principle, done here by an invariant, and a picture of two graphs will always leave a reader wondering whether one is the other rotated.

The idealisation, named #

The discs are circles and the sheet is a square with sharp corners, which is the model the whole method rests on. What matters here is subtler: a contact is an idealisation of its own. In the model two discs either touch or do not; in a folded model the corresponding creases either meet or leave a sliver of paper, and a sliver of paper is a real thing that shows up as a small flap nobody wanted.

So the tolerance question is not an artefact of the arithmetic. A designer building from an approximate packing has to decide which near-contacts to treat as contacts, and the decision is a design decision with consequences in paper — which is the practical content of the plateau measurement.

The generalisation #

An optimiser reports the objective, and the objective is rarely the answer. The radius is what the search maximises and the graph is what the design needs; the two are related by the arrangement, and the relation is not a function. That is a common shape — the value of a solution being a coarser thing than the solution — and it is invisible as long as the objective is the only thing recorded.

The practical rule is short. Record the arrangement, not the number. A packing table that gives radii is a table nobody can build from; two lines of contacts per entry would make it one. And where the arrangement is only approximate, record the tolerance at which the contacts were read, because the graph is a function of it.

The uncomfortable half is that this is not a failure of the search. The search did what it was asked; the question which of the equally good arrangements is this one was never posed, and at five and six flaps there is more than one answer.

Where the ladder goes next #

The obvious continuation is to build the patterns, and the construction that would do it is already here. Two contact graphs at one radius are two crease patterns, and comparing them — their crease lengths, their vertex counts, their folded footprints — would say whether the difference matters to a folder or only to a bookkeeper.

That step needs exact packings rather than searched ones, which is the harder half of the subject and where the difficulty has sat since the method was invented. Until then, what can be said is what is said above: the number a search reports does not determine the design it found, at least at some flap counts, and nobody looking at the number can tell which.