Origami & Folding
what one sheet can do
Rigid folding

Two refusals that refuse differently

Four of the six developable quadrilateral meshes this collection solves have no ordering of their nine panels — they must pass through themselves, and a search over every ordering proves it. On all four, the letters agree with themselves perfectly. The linear proof and the exponential search are not a fast test and a slow one: they answer different questions, and neither contains the other.

Assumes A collision is an order and A proof in one pass.

20 min read 8 figures Local rules, global behaviourFrom craft to hardware

A collision is an order established something uncomfortable about the meshes this collection solves for rigid folding. Six developable quadrilateral meshes, each with no two vertices alike, each satisfying every condition at every interior vertex — and four of them have no ordering of their nine panels at all. Every arrangement of the pile breaks one of the non-crossing rules, so every one of those four must pass through itself, and it was proved by searching every ordering rather than by driving the mesh and watching for a collision.

Since then a second test has arrived that also proves a pattern cannot be folded flat, and proves it in one pass over the crease list. The obvious question is what it makes of the same six.

Nothing

The refusal the letters can see, and the one only a search canSix developable quadrilateral meshes, each asked twice whether its panels can be stacked: once by reading the arcs its letters force, and once by searching every ordering. The letters agree with themselves on all six; the search refuses four of them.the bar is the nodes the ordering search visitedthe letters are consistent on every one of these, so the one-pass test says nothing about any of themmesh 37,4739 panels · 7,473 nodes · no order existsmesh 58,0079 panels · 8,007 nodes · no order existsmesh 89,3469 panels · 9,346 nodes · no order existsmesh 111,0159 panels · 1,015 nodes · an order existsmesh 141449 panels · 144 nodes · an order existsmesh 199,0629 panels · 9,062 nodes · no order existsa red bar is a pattern with no folded state, found only by visiting every ordering it might have had
Fig. 1 Six developable quadrilateral meshes, each asked twice whether its panels can be stacked: once by reading the arrows its letters force, once by searching every ordering. The search refuses four. The letters of all six agree with themselves.

The cheap test is silent on all six. Not nearly firing, not firing on the easy ones — silent, including on the four that are provably unfoldable.

That is worth sitting with, because it is not the relationship one expects between a cheap sound test and a complete one. The usual picture is a sieve: the cheap test catches the obvious cases and the expensive one is reserved for what falls through. Here the cheap test catches nothing the expensive one catches, on this population.

What each one is reading

It is worth first ruling out the boring explanations, since a test that fires on nothing invites them.

It is not that the test is broken. It fires on other patterns, and it fires on relettered versions of these: the fourteenth mesh, relettered sixty times, produces eleven letterings whose letters contradict themselves. So the machinery works and it works on these very meshes; it is the letterings they arrive with that it has nothing to say about.

It is not that the meshes are too small. Nine panels is enough for a contradiction — the square twist manages one with nine — and the meshes have six independent chains of panels, which is more than the twist’s four.

The bigger the patch, the rarer a lettering that agrees with itselfThe same twist construction over five tilings, ordered by how many panels the folded patch has, against the share of independently drawn letterings whose letters do not contradict themselves. The share falls to nothing well before the patch is large enough to be interesting.the bar is the share of draws that agree with themselvesthe rows are ordered by panel count, which is the only thing changing along them49 panels26 of 200square · 84 creases · 26 of 20062 panels5 of 200elongated · 106 creases · 5 of 20077 panels2 of 200hexagonal · 142 creases · 2 of 20083 panels0 of 200triangular · 142 creases · 0 of 200157 panels0 of 200rhombille · 282 creases · 0 of 200a zero is a zero of the draws taken and not a proof that no consistent lettering exists
Fig. 2 What each one is reading, across the sizes: how often a redrawn lettering agrees with itself as the patch grows. The cheap refusal reads this and the expensive one does not, which is why they disagree about which patterns are hard.

The two tests are given different parts of the same object, and that is the whole explanation.

The layer refusal reads the letters. Each crease says which of the two panels it joins lies above the other — a valley brings the far panel over, a mountain takes it under, and turning the near panel over swaps which — and a chain of panels each of which must lie below the next is a proof that no order satisfies all of them. Nothing in that consults where the paper landed.

The ordering search reads the folded state. It needs every panel placed, then every pair of panels tested for shared ground, and then it explores arrangements against three kinds of constraint: the one the letters encode, plus two more that only exist once the geometry is known. A panel may not lie between the two panels a crease joins where that crease’s image crosses it. Two creases whose images lie along one line and overlap may nest or stand clear but may not interleave.

Which of the two rules holds each sheet downThe non-crossing rules a folded pattern generates, split by kind: a panel that a crease's folded image runs through, and two creases in the same place that must not interleave. Two of the eight patterns generate none of the first kind and are governed entirely by the second.the bar is every non-crossing rule the folded state generatesThe preliminary base120 through a fold · 12 interleavingThe Miura fold228144 through a fold · 84 interleavingThe square twist4836 through a fold · 12 interleavingThe hexagon twist9690 through a fold · 6 interleavingThe Yoshimura pattern11870 through a fold · 1187 interleavingFold and cut — the triangle1512 through a fold · 3 interleavingThe tapered corrugation351308 through a fold · 43 interleavingThe waterbomb tessellation654144 through a fold · 510 interleavinga pattern whose creases never land inside another panel generates none of the first kind
Fig. 3 The three kinds of constraint, counted for each printed pattern. The first column is read off the letters; the other two are found by testing panels against one another, and they are what refuses the four meshes.

So the four meshes fail for reasons in the second and third columns. Their letters are fine. Their panels simply cannot be got past one another in the plane they land in, and no amount of reading the crease list discovers that.

A cheap test that fires on these would have to see the overlaps

It is worth being concrete about what a cheap test would need in order to catch the four meshes, because the answer explains why there is not one.

The rule that refuses them says: this panel may not lie between those two, because a crease’s folded image runs across it. Finding that out means knowing where the crease’s image is, which means having placed every panel, which means composing reflections along a spanning tree of the panel graph — cheap, as it happens, and linear. Then it means testing which panels the image crosses, which is every crease against every panel.

That much is polynomial and this collection computes it. What is not polynomial is what comes next. The rules generate a set of statements of the form not between, and deciding whether some total order satisfies all of them at once is not a matter of looking for a contradiction among pairs — three statements can be individually satisfiable and jointly not, in a way no pairwise reading detects.

The layer refusal escapes that because its statements are all of one shape: this below that, which is a relation, and a relation is unsatisfiable exactly when it has a circle. The betweenness statements are not a relation and have no such characterisation.

Every contradiction has an even number of panels in itThe length of every circle found in the layer relation, over every population of crease patterns here. No odd length occurs, because the panels of a flat-foldable pattern two-colour; and no length of four occurs, because a circle of four goes round one vertex and the counting theorem closes it.the bar is how many circles of that many panels were found726 circles, from 6 panels to 32, over every pattern family measured here4 panels0round one vertex — Maekawa forbids it5 panels0odd — the two-colouring forbids it6 panels21129.1% of the circles measured7 panels0odd — the two-colouring forbids it8 panels21129.1% of the circles measured9 panels0odd — the two-colouring forbids it10 panels8211.3% of the circles measured11 panels0odd — the two-colouring forbids it12 panels9513.1% of the circles measured13 panels0odd — the two-colouring forbids it14 panels304.1% of the circles measured15 panels0odd — the two-colouring forbids it16 panels314.3% of the circles measured17 panels0odd — the two-colouring forbids it18 panels172.3% of the circles measured19 panels0odd — the two-colouring forbids it20 panels141.9% of the circles measured22 panels81.1% of the circles measured24 panels152.1% of the circles measured26 panels71.0% of the circles measured28 panels20.3% of the circles measured30 panels20.3% of the circles measured32 panels10.1% of the circles measuredthe empty rows are not rare cases — they are lengths that cannot occur, and each has its own reason
Fig. 4 A cheap test that fires on these would have to see the length of a contradiction: every circle found anywhere in this collection, by how many panels it runs round. A rule about two panels cannot see a circle of six.

The gap between them is a known boundary

The section above says the betweenness statements are not a relation and have no cheap characterisation, and leaves that as an observation about what nobody has found. It is stronger than that: constraints of exactly this shape define a problem that is known to be intractable, and the boundary between the two tests is that boundary rather than a gap in anybody’s ingenuity.

Sort the constraints by how many panels each mentions. The crease rule mentions two: this one below that one. A collection of such demands is a relation on the panels, and a relation admits a total order exactly when it has no cycle — which is a walk over a graph, linear in the number of demands, and is precisely the cheap test.

The other two rules mention three or four. This panel may not lie between the two that crease joins is a statement about which of three elements sits in the middle, and a set of such statements is a betweenness system. Deciding whether a betweenness system admits a total order at all is NP-complete, and has been known to be since the late nineteen-seventies — it is one of the standard hard ordering problems, and it is hard for the reason the essay identifies by hand: three demands can be individually satisfiable and jointly not, in a way no reading of pairs detects.

Which says the cheap test cannot be widened

That converts the closing paragraph’s honest summary into a statement with a reason under it.

The layer refusal is cheap because it reads the only constraints in the problem that are binary, and binary constraints have a cycle characterisation. Widening it to catch the four meshes means reading the ternary ones, and reading the ternary ones is the hard problem — not a harder version of the cheap one, but a different complexity class of question that happens to be phrased in the same vocabulary.

So there is no prospect of a cleverer pass over the crease list that catches what the search catches. Any test that refuses the four meshes has either solved a betweenness system, which is intractable in general, or has found a special structure in these particular meshes that does not generalise.

That also explains why the split is so clean rather than being a matter of degree. The two tests are not two points on a scale of thoroughness; they are on opposite sides of the line where a problem stops having a local certificate. The cheap test is complete for the binary part and blind to the rest, and the rest is where the difficulty of the whole subject lives — which is the same statement the hardness construction makes about flat-foldability, arriving here as a fact about which of three columns of constraints a test is allowed to read.

The two failures are not two grades of one failure

It would be tidy if the letters caught the severe cases and the search the marginal ones, and it is worth checking whether that is what is happening. It is not.

The meshes the search refuses fail comprehensively: there is no ordering, not a fragile one. And the patterns the letters refuse — a tessellation patch with a contradictory lettering — fail comprehensively too, with the contradiction spread over half the panels.

They are two disjoint kinds of impossibility. One is combinatorial: the letters make demands that cannot all hold. The other is geometric: the demands are consistent and the paper is in the way.

Which is which, on the shelf

Across the patterns this collection prints, the same division holds and the numbers say how lopsided it is.

On the square twist, of the two hundred and fifty-six labellings that pass every vertex condition, four are refused by their letters and two hundred and forty-four more by the non-crossing rules. On the fold-and-cut triangle, twelve labellings are refused and the letters catch none of them. On the preliminary base nothing is refused at all.

So on every pattern where both can be run, the geometric refusal is the larger by a wide margin, and the combinatorial one is between nought and two per cent of the total. Consistent is not foldable is that measurement in full.

What the meshes are, and why they are the sharp case

The quadrilateral meshes are the right population for this comparison and it is worth saying why.

They are built to be developable and flat-foldable at every vertex — the family the Miura belongs to, with the vertices perturbed so that no two are alike. So they pass the local conditions by construction, which removes the first refusal from consideration entirely.

They are small: nine panels, so the search finishes and gives a definite answer rather than a refusal. That is rare — a Miura of twenty-four panels defeats it, and so does every printed pattern past twelve.

And their letters are derived rather than chosen. The solver computes fold angles and reads the letters off their signs, so the labelling each mesh carries is the one a physical folding produces. A labelling obtained that way cannot contradict itself, because a folding is an ordering and an ordering is what a contradiction proves does not exist.

The same rule, three sheetsThree crease patterns built by one rule: draw a fan of straight lines, then a row that reflects in every one of them. That reflection is Kawasaki at each vertex, so the pattern is flat-foldable before anything has been checked — and the fan's angle is the only thing that differs between them.parallel columnsKawasaki to 3e-14°columns fanning by 5.7°Kawasaki to 5e-14°columns fanning by 11.5°Kawasaki to 1e-13°the mountain-and-valley letters are read off the motion rather than drawn, and then put past Maekawa
Fig. 5 The family: developable quadrilateral meshes with every vertex different, each solved to within a millionth of a radian. Four of the six place perfectly and cannot be stacked.

That last point is the one that makes the silence unsurprising in retrospect. The cheap test could never have fired on these, because the construction that produced them supplies exactly the kind of labelling the test looks for a fault in.

What the four meshes are actually doing

The proof that a mesh cannot be ordered is a proof that it must pass through itself, and it is worth saying what that means for something that is meant to be a rigid folding.

Paper through paper is the standing complaint about every rigid-folding test here: the tests are statements about a neighbourhood, a neighbourhood cannot see the far side of the sheet, and a mesh can satisfy all of them while driving one panel straight through another. Closing is not building turned that into a measurement by following the motion and watching for the crossing.

The ordering search is the same complaint answered at the flat state, where there is nothing to watch. The fold is over, the panels are where they are going, and the question is a property of the arrangement rather than an event. So the four refusals are proofs that these meshes pass through themselves somewhere, obtained without following any motion at all — and the letters, which are what a rigid solve produces, have nothing to say about it.

That division is not incidental to rigid folding; it is the shape of the subject. A rigid motion is decided by angles and a layer order is decided by which panel is on top, and the two are different objects with different tests.

Which test to run

The practical answer is both, and always in the same order, and the reason is not that one is a filter for the other.

Run the layer refusal first because it is free — one pass over a crease list, no folded state required, no overlap scan. Where it fires it is done, with a reason attached that names panels. Where it does not fire it has cost nothing and nothing has been learned, which is a perfectly good outcome for a test that costs nothing.

Run the search where the pattern is small enough. On anything past about twenty panels it is not a slower answer but no answer: it visits two million nodes and reports that it does not know.

The refusal the letters can see, and the one only a search canSix developable quadrilateral meshes, each asked twice whether its panels can be stacked: once by reading the arcs its letters force, and once by searching every ordering. The letters agree with themselves on all six; the search refuses four of them.the bar is the nodes the ordering search visitedthe letters are consistent on every one of these, so the one-pass test says nothing about any of themmesh 37,4739 panels · 7,473 nodes · no order existsmesh 58,0079 panels · 8,007 nodes · no order existsmesh 89,3469 panels · 9,346 nodes · no order existsmesh 111,0159 panels · 1,015 nodes · an order existsmesh 141449 panels · 144 nodes · an order existsmesh 199,0629 panels · 9,062 nodes · no order existsa red bar is a pattern with no folded state, found only by visiting every ordering it might have had
Fig. 6 Which test to run: the refusal the letters can see beside the one only a search can, on the same patterns. One is a single pass over the crease list and the other visits orderings, and they do not catch the same things.

So on a small pattern both run and the search decides. On a large one only the cheap test runs, and its silence is the only thing available — which means that for a tessellation patch, nothing this collection owns can distinguish between a pattern that folds and one whose panels cannot be got past one another. A reader who folds one has better evidence than any of it.

Where the letters do fire, and what those patterns look like

For contrast it is worth naming the patterns the cheap test does refuse, since a test that is silent on six meshes is easy to write off.

It refuses tessellation patches, and it refuses them at a rate that makes them unusable without a redraw: twenty-six letterings of two hundred agree with themselves on a square patch of forty-nine panels, none of two hundred on a rhombille of a hundred and fifty-seven. Those are patterns with thirty-six to a hundred and twenty-six independent chains of panels, and a chain is what a contradiction needs.

The meshes have nine panels and six chains. So the population that makes the cheap test look useless is the population where a contradiction has almost nowhere to sit, and the population where it earns its place is the one no search can touch.

How much room a pattern gives its letters to disagreeEvery pattern family here plotted by how many independent closed chains of panels it has against how often an independently drawn lettering agrees with itself. The count is Euler's relation on the panel graph and equals the number of interior vertices; it is read off the drawing before any letter is chosen.more chains is more chances for one of them to closethe printed shelftessellation patchesfold-and-cut outlinessheets folded at random00.2500.5000.7501255075100125independent closed chains of panelsshare of letterings that agree with themselvesa point at nought is nought of the draws taken, which is not a proof that no consistent lettering exists
Fig. 7 Four families by how many independent chains their panels form. The quadrilateral meshes sit at the left with the fold-and-cut outlines; the patches are at the right.

That is the reconciliation, and it is worth stating in one line. The two tests are strong in opposite regimes: the search decides small patterns completely, and the letters are the only thing that speaks at all on large ones — and there is no pattern anywhere on which both are informative.

A third refusal, for completeness

There is a test between the two that this collection owns and that has not been mentioned, and leaving it out would make the pair look starker than it is.

The placement check asks whether the panels close: compose the reflections round every loop of panels and require the composition to be the identity. It is a walk over the panels, so it is cheap, and it reads the drawing and the letters together while consulting no overlap.

It refuses none of the six meshes and none of the printed patterns — they all close to about a quadrillionth — and it refuses tessellation patches assembled the wrong way outright. So it is a third disjoint refusal: geometric like the search, cheap like the letters, and catching a class neither of them touches.

Three cheap tests reading three different parts of the input, one expensive test reading all of it, and no overlap between what the cheap ones catch. That is the actual shape, and it is a good deal less tidy than a sieve.

What is missing between them

The gap is not a matter of effort and it has a name.

Everything the layer refusal reads is a fixed list of statements about pairs of panels — one per crease, known before anything is placed. Everything the search reads is a set of constraints generated by overlaps, which are quadratic in the panels and cannot be known until the folded state has been computed. There is no polynomial test in this collection that reads the second kind of constraint and returns a proof.

Whether one can exist is the hardness of the problem restated: a short certificate for no folded state exists is roughly what a fast complete test would need, and nobody has one. The layer refusal is a short certificate for a special case, and its special case is exactly the one the geometry never enters.

How often a redrawn lettering is consistent with itselfIndependent letterings drawn from each pattern, and how many of them the letters do not contradict. A pattern this site prints is nearly always consistent whatever letters it is given; a tessellation patch cut from the same construction almost never is.the bar is the share of draws whose letters agree among themselvesa draw that disagrees is a proof that the pattern has no flat folded state with those lettersthe preliminary base200 of 2008 panels · 8 creases · 0 contradict themselvesthe square twist198 of 2009 panels · 12 creases · 2 contradict themselvesthe Yoshimura190 of 20065 panels · 86 creases · 10 contradict themselvesthe Miura fold181 of 20024 panels · 38 creases · 19 contradict themselvesa square twist patch26 of 20049 panels · 84 creases · 174 contradict themselvesa hexagonal patch2 of 20077 panels · 142 creases · 198 contradict themselvesa rhombille patch0 of 200157 panels · 282 creases · 200 contradict themselvesthe sampler returns solutions rather than a uniform draw over them, so these are shares of what it found
Fig. 8 The share of drawn letterings that agree with themselves, over seven patterns. Everything above the line is where the search can be run; everything below is where it cannot.

The honest summary is that this collection now owns one proof of failure that is cheap and narrow, one that is complete and unavailable at scale, and nothing in between. The four meshes are the demonstration that the first cannot be widened by trying harder — they are the simplest patterns available on which it must be silent, and it is.

Where this goes next

the bar is the share of the population with a folded stateevery pattern in all four passes every condition at every interior vertexthe printed patterns4 of 80 cannot be placed · 0 cannot be ordered · 4 undecidedtwist tessellations2 of 125 cannot be placed · 2 cannot be ordered · 3 undecidedquadrilateral meshes2 of 60 cannot be placed · 4 cannot be ordered · 0 undecidedfold-and-cut patterns5 of 70 cannot be placed · 0 cannot be ordered · 2 undecidedundecided is a real answer here and is not rounded toward either side A collision is an order Paper passing through paper is treated here as a thing that happens during a motion and is caught by watching for it. At the flat state it is not an event at all: it is the absence of an ordering, and it can be proved rather than observed. Four of the six quadrilateral meshes this site solves for rigid folding place perfectly and admit no ordering of their nine panels — so every one of them must pass through itself, and none of them was ever driven to find out. the square twist, sieved three timesevery lettering4,0962 to the 12passes every vertex2566.3% of themletters are consistent2524 force a loop of panelshas a folded state80.20% of themthe bars are on one scale, so the last one is the size of the answer against the size of the question Consistent is not foldable The square twist has 4,096 mountain-valley labellings. Two hundred and fifty-six satisfy every condition at every vertex; two hundred and fifty-two of those have letters that do not contradict themselves; and eight have a folded state. So the cheap proof that reads the letters in one pass accounts for four of the two hundred and forty-eight failures, and the other two hundred and forty-four are refused by a search over orderings that nothing shorter replaces. the bar is how many of the 38 patterns each refusal is the first to catchtwo creases cross5one sweep over pairs of creasesa vertex condition fails0one pass over the verticesthe panels do not place0one walk over the panelsthe letters force a loop1one pass over the crease listno ordering exists6every ordering of the panels26 of the 38 are refused by none of these and are folded, undecided, or waiting on a search too large to run The refusal that reads the list once There are five ways of saying no to a crease pattern here, and their costs are two hundred and eighty-two, a hundred and twenty-six, a hundred and fifty-seven, thirty-nine thousand six hundred and twenty-one — and a search that is refused outright. On the largest patch the four cheap tests together do less work than one of them looks like it should, and the fifth cannot be started. A refusal that reads the crease list once is the only kind that scales.

What this makes readable

Essays that name this one as a prerequisite.

Named alongside this one

Essays reaching for the same objects. Nobody chose these; they are what the concept index makes visible.

What links here

The 8 essays that link to this one and share the most of its objects, of 11 that link here.

The objects this essay names

Each one links to every other essay that touches it.

Decision procedureEnumerationLayer orderingNecessary conditionNon-crossing conditionQuadrilateral meshSearch costSelf-intersection