A collision is an order

Paper through paper is the standing complaint about every test this subject has for rigid folding: the tests are statements about a neighbourhood, a neighbourhood cannot see the far side of the sheet, and so a pattern can satisfy all of them while driving one panel straight through another. Closing is not building turned that into a measurement — six meshes solved to within a millionth of a radian, one of which drives a panel through another at every angle of its motion — by following the motion and watching for the crossing.

Watching is the right method during a motion. At the flat state it is the wrong one, because there is nothing to watch: the fold is over, the panels are where they are going to be, and the question of whether the paper passes through itself is not an event but a property of the arrangement.

It is also decidable.

The rules are the collision test #

A flat folded state is a set of panels lying in a plane with a pile of layers over each point, and “the paper does not pass through itself” is exactly three statements about that pile.

A crease decides its own pair. The two panels a crease joins are the paper turning over; one is above the other and which is fixed by the letter and by whether the near panel has been turned. Ordering them the other way is the paper turning the wrong way, which is not the crease that was drawn.

A panel may not pass through a fold. Where a crease’s folded image runs across the interior of another panel, that panel cannot lie between the crease’s own two. The crease is where the paper turns; there is no gap in it.

And two folds in the same place may not interleave. Two creases whose images lie along one line and overlap are two U-turns in the same place, and they may nest or stand clear but not link.

Every one of the three is a necessary condition, and together they are what “no self-intersection” means for a flat state. So a search over the orderings of the panels that exhausts itself and returns nothing has proved that the sheet must pass through itself somewhere. Not “no arrangement was found”: none exists.

What the meshes say #

This repository keeps six developable quadrilateral meshes, built to be handed to the rigid-folding solver. Each is nine panels; each satisfies every condition at every interior vertex; each places consistently, with the two routes to any panel agreeing to fifteen decimal places.

Four of the six cannot be ordered. Their panels go down exactly where the reflections put them, and there is no way to pile them that satisfies all three rules — so each of the four, if it were made of paper and pushed flat, would have to have paper somewhere on both sides of paper.

That is a much stronger statement than anything the motion-following method produced, and it costs a search over 362,880 arrangements rather than a swept simulation. It is also a statement about the flat state only: nothing here says where along a motion the trouble starts, or whether a mesh that cannot be flat can be folded partway.

Why the meshes and not the shelf #

The two populations behave completely differently and the reason is what each was assembled for.

The printed shelf is eight patterns chosen because a reader should be able to fold them. Four are small enough to decide and all four have an ordering; the other four are undecided. Nothing on it is refused.

The meshes exist to be solved, which is a different question with a different answer. A quadrilateral mesh is handed to the solver, which asks whether its fold angles can be made consistent all the way round every vertex along a continuous motion — and that condition is not flat-foldability. A mesh satisfying it has a rigid motion. Nothing in it asks what happens to the layers when the motion arrives at flat.

So the four refusals are not defects in the meshes. They are what happens when a set built for one property is asked about another, and the honest reading is that rigid-foldable and flat-orderable are independent on this evidence: four of six have the first and not the second.

The count that goes with it #

The third column is the mechanism, and it very nearly sorts the table.

The two meshes that fold generate thirty-five and forty-four rules. Three of the four that do not generate forty-five, fifty-two and fifty-three. The exception is mesh 19 at forty-two, which is refused while mesh 11 at forty-four is not, so this is a tendency and not a threshold — and it is worth saying plainly that a tendency over six patterns is barely evidence at all.

What the count does explain is why nine panels can be impossible. Nine panels admit 362,880 orderings; forty rules, each removing a constant fraction of what is left, remove essentially all of them. The same arithmetic on the printed patterns leaves one ordering standing; on these it leaves none.

The difference between one and none is the whole of it. A pattern whose rules leave exactly one arrangement folds, in exactly one way, and cannot be argued with. A pattern whose rules leave none does not fold at all, and the two are separated by a single constraint.

The twist that is too small #

The twist population gives the same finding with a parameter attached, and the parameter is one a designer chooses.

A square twist at a radius of 0.3 sheet widths has no ordering of its nine panels. The same twist at 0.5 and at 0.7 does. Nothing else changes between them — the same nine panels, the same four interior vertices, the same construction, the same letters chosen the same way. Only the central polygon’s size.

That is a fence a designer can cross without noticing, and this site has met two of its kind on the twist family already: past a certain turn the pleats have no paper left, and below a certain turn the pattern loses its mountain-valley assignment entirely while every angle condition goes on holding. Neither of those is this one. A twist at 0.3 has an assignment, has its angles, has everything the earlier fences test for, and its panels cannot be piled.

So the twist family has a third fence, it is at a different place from the other two, and it was invisible to every gate the site had.

What this does not replace #

The motion-following method is not superseded and this is the wrong reading of the result.

A collision along the way is invisible here. A mesh whose flat state is perfectly orderable can still drive a panel through another at an intermediate angle, and one of the six does exactly that at every angle of its motion. The flat state is one point of a continuum, and a test that only looks at the endpoint sees one point.

And a mesh that never reaches flat is not covered at all. Several of the objects this subject cares about are not folded flat in use — a deployable stops at a working angle — so their flat state may be irrelevant even when it exists.

So the two methods answer different questions with different strengths. Following the motion gives an angle and a pair of panels and no proof; searching the flat orderings gives a proof and no angle. A pattern that passes both has been asked more than either alone can ask.

Where a proof is worth more than an observation #

There is a practical reason to prefer the proof where it is available, and it is not elegance.

A simulation that finds no collision has found no collision at the angles it sampled. Sampling a motion is a choice of step size, and a panel that grazes another between two samples is missed — which is the standing weakness of every numerical sweep and the reason a sweep that jumps between branches has to refuse rather than draw.

The ordering search has no step size. It enumerates a finite set exhaustively and either finds a member or shows the set is empty. Where it applies, “no collision” and “collision” are both certain, and the only uncertainty left is the one it declares: patterns too large to enumerate come back undecided, and eight of the thirty-one patterns in these populations do.

The cheap half of the proof #

One of the three rules is testable without any search, and it is the only part of this that reaches the patterns anybody builds.

The crease rule fixes one relation per crease, so the letters give a directed graph on the panels with one arc per crease. A cycle in that graph is a proof of failure in one pass — no ordering can satisfy a loop of inequalities — and it costs the same on a hundred panels as on nine.

None of the six meshes has one: their letters are consistent among themselves and the failure is in the other two rules, which need the search. That is the usual case. Where a cycle does appear it is decisive, and the same test found one in a forty-nine-panel patch of twist tessellation that no enumeration could ever have reached.

Twelve of thirty-one, across the four populations #

Widening the view past the meshes changes the emphasis rather than the conclusion.

Across the printed shelf, the twists, the meshes and the cut sheets there are thirty-one patterns. Twelve are known to have an ordering. Six place and admit none. Five do not place at all — their reflections around a loop of panels do not compose to the identity, so there is no consistent flat arrangement to order. Eight are past what the search will finish.

The five that do not place are a different failure and they belong to a different rung: it is not a collision, it is that the paper cannot be put down. The six that place and cannot be ordered are collisions, proved, and four of them are the meshes.

So proved self-intersection at the flat state is not rare in the material this site keeps — one pattern in five of everything the machinery is run over. What made it look rare is that nothing asked.

Three things this does not say #

It does not say the four meshes are wrong. They are rigidly foldable, they were built to be, and they are correct examples of the thing they are examples of. What they are not is flat-foldable, and nothing before this asked.

It does not give a rate. Four of six is four of six. Six meshes assembled by hand for another purpose is not a sample of quadrilateral meshes.

And it does not locate the collision. The search says no ordering satisfies the rules; it does not say which two panels are the trouble, and a report naming a pair would need a different computation — the minimal unsatisfiable subset of the constraints, which this file does not compute.

Locating the collision is one search per rule #

The last caveat says the search does not name the panels, and that a report naming a pair would need a computation this collection does not do. The computation is available and it is the same search run again, which is worth setting out because it turns a verdict into a diagnosis.

A set of rules with no solution has a minimal unsatisfiable subset: a smallest collection of them that is already impossible, so that removing any one of it makes the rest satisfiable. Finding one needs no new machinery. Delete a rule, re-run the search, and see what happens. If the pattern becomes orderable, that rule was essential and goes back; if it stays unorderable, the rule was redundant and can be dropped for good. Sweep once through the list and what is left is minimal.

The cost is one search per rule. On these meshes that is about fifty searches of three hundred and sixty thousand arrangements each, which is the same order of work as the enumeration already reported and finishes in about the same minute. There is nothing clever in it and nothing to write beyond a loop.

What the subset would say #

The output is the diagnosis a designer wants, and it is more specific than a pair of panels.

A minimal subset is a handful of rules — typically three or four, since a smaller number of inequalities is easier to contradict than a larger one — and each rule names two panels and a reason: this crease turns this way, this panel cannot lie between these two, these two folds may not interleave. So the report is a short list of the form these five panels, these four demands, and no order satisfies them all.

That is checkable by hand. A reader given four inequalities on five panels can verify in a moment that they contradict, which makes the refusal a certificate of the kind a short reason to say no is about — an object handed over rather than an assurance that a search looked everywhere.

It would also settle the rule-count tendency the table gestures at. Three of the four refused meshes generate more rules than either that folds, and the exception at forty-two makes the reading a tendency over six patterns. If the minimal subsets came back at a consistent size — four rules on every refused mesh, say — the count of all the rules would stop being the interesting number, and the shape of the small contradicting set would take its place. Six patterns cannot establish that either, but they can produce the six subsets, and six subsets are a much more informative object than six totals.

What the refusal is worth as a gate #

The practical consequence for this collection is a gate it did not have, and it is worth saying where it now sits.

Any pattern this site prints at true scale is a pattern a reader is invited to fold, and until now the invitation rested on the vertex conditions. It now rests on those plus, where the pattern is small enough, an exhaustive search over the orderings of its panels — and where it is not small enough, on the cheap loop test and an honest undecided printed beside it.

That gate has already caught two printed patterns and would have caught them at any point since the shelf was first printed. It is not a new insight into folding; it is a question that existed the whole time with nothing pointed at it, which is the shape of most of what the new instrument found.

And the gate can fail. It refuses a pattern that has no ordering, and it says nothing about a pattern that has one — because an ordering satisfying these three rules is a candidate and the general decision is intractable. A gate that only ever passes things is not a gate; this one refuses eleven of thirty-one, which is why it is worth having.

What a folder should take from it #

At the flat state, a collision is a missing order. There is nothing to watch for and nothing to sample; the arrangement either exists or it does not, and which of those is decidable on a small pattern.

Solved is still not built. A mesh whose fold angles close has passed a condition about angles. Four of the six here pass it and have no flat pile, which is a second way for a solved mesh not to be an object.

And a proof is worth pursuing where the pattern is small. Nine panels is 362,880 arrangements and a second of arithmetic. Twenty-four is neither, and the honest answer there is the one the search gives — the same undecided that every counting argument on this site runs into.