Origami & Folding
what one sheet can do
Concept

Decision procedure — where it appears

A method that answers yes or no rather than testing a condition and reporting what it found. The crimp reduction is one for a single vertex, and a procedure is a different kind of answer from a test: it decides the case rather than failing to rule it out.

Named by 15 essays across 5 fields — each of them below, with the objects they name alongside it.

the waterbomb tessellation's odd vertexdegree six, and this site prints nine of them on one sheetevery assignment64passes all four conditions30has a flat folded state1812 labellings satisfy every condition the subject has and have no flat folded state

Crimp it away and ask again

Four conditions decide whether a vertex folds flat, and they decide it exactly at a vertex whose sectors are all different sizes. Everywhere else they over-count: two markings of every tied four-crease vertex, twelve of the degree-six vertex this site prints nine of on one sheet. What decides the case is not a fifth condition but a procedure — fold the smallest sector away and ask the smaller vertex.

flat-folding · Crimping every condition holds here6 creases4 creasesevery condition holds at the vertex on the paper — and one crimp later the smallest sector has the same letter on both sidesthe four conditions all hold · a stacking does not exist

A short reason to say no

When a folding question comes back yes it brings an object anybody can check. When it comes back no it usually brings nothing but the assurance that a search looked everywhere. At one vertex that is false: a refusal comes with a witness one or two steps long, out of a search space of a hundred and twelve, and the witness is a vertex the crease pattern does not contain.

complexity · Hardness of folding degreevertices visited per letteringcrimps needed48 of 16 fold32630 of 64 fold1038112 of 256 fold41410420 of 1024 fold2065121584 of 4096 fold12376The work grows by a factor of about 6.0 for every two creases added; the necessity grows by one.

A tie is not a decision

The crimp reduction decides a vertex by folding its smallest sector away, and where two sectors tie for smallest it has no forced move and must try each of them. That search is not rare — on the vertex at the centre of the first base anybody folds it happens for fourteen of the sixteen letterings — and it has never once changed the answer.

flat-folding · Crimping 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

The patterns a checker is tested on

This site keeps four populations of crease patterns and runs its checkers over them, which is what makes a claim about typical instances measurable rather than rhetorical. Asked whether the members actually fold, the populations answer: thirteen of thirty-three do, six place and cannot be ordered, five cannot be placed at all, and nine are past what the search will finish.

complexity · Typical instances the bar is how many of the 33 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 loop0one pass over the crease listno ordering exists6every ordering of the panels22 of the 33 are refused by none of these and are folded, undecided, or waiting on a search too large to run

The order the refusals come in

This collection can say no to a crease pattern in five ways, and they cost wildly different amounts: a sweep over pairs of creases, a pass over the vertices, a walk over the panels, a pass over the crease list, and an enumeration of every ordering of the panels. Run all five over the thirty-three patterns in the four test populations and the cheapest refuses five, the most expensive refuses six, and the three in between refuse nothing at all.

complexity · Hardness of folding the bar is the share of random drawings with at least one crossing in them2 segments23.1%0.23 crossings on average3 segments51.2%0.69 crossings on average4 segments73.5%1.36 crossings on average6 segments95.2%3.48 crossings on average8 segments99.4%6.53 crossings on average12 segments100.0%15.30 crossings on average20 segments100.0%43.76 crossings on averageevery crease pattern in this collection has none, and none of them was drawn at random

Drawn by the same hand

Two straight segments dropped on a square cross about 23% of the time; four of them cross 74% of the time; twelve cross with certainty, about fifteen times over. Every crease pattern in this collection's four test populations has none — not because the checkers were catching them, but because the same rules that drew the patterns were incapable of producing one, and nothing looked until a construction finally did.

complexity · Typical instances the bar is how many folds the alignment names, averaged over the trialsa1 — the fold through two points1.000.0% none · 0.0% twoa2 — one point onto another1.000.0% none · 0.0% twoa3 — one line onto another2.000.0% none · 100.0% twoa4 — a perpendicular through a point1.000.0% none · 0.0% twoa5 — a point onto a line, through a point1.5223.8% none · 76.2% twoan alignment with no fold is not a failed construction; it is an alignment the paper cannot make

An axiom may name no fold

The seven operations are stated about points and lines in a plane, and a plane has no edges. On a square, three of them always name exactly one fold and always land it on the paper; placing a line on a line names two, and 13.3% of the folds it specifies are creases the sheet never reaches; and placing a point on a line through a second point names two folds, one, or — 23.8% of the time — none at all.

construction · The axioms 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

A proof in one pass

Deciding whether a crease pattern has a flat folded state is hard, and the search that decides it gives up at twenty-four panels. One line of the same machinery does not search at all: each crease says which of the two panels it joins lies above the other, and a circle in what those statements demand is a proof that no folded state exists. It costs one pass over the crease list, and on a tessellation patch of a hundred and fifty-seven panels it answers in milliseconds.

flat-folding · Forced order 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.

flat-folding · Layer multiplicity 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.

complexity · Hardness of folding the bar is the mean share of redraws that agree with themselvesas the populations stand, every member is consistent and the refusal fires on none of themthe printed patterns96.7%8 of 8 could be asked · worst member 90%twist tessellations55.0%7 of 12 could be asked · worst member 7%quadrilateral meshes96.9%6 of 6 could be asked · worst member 82%fold-and-cut patterns100.0%7 of 7 could be asked · worst member 100%a member with no folded state has no letters to redraw and is counted as not asked rather than as passing

A population that cannot fail

Thirty-three crease patterns are kept here to run the checkers over, and every one of them has letters that agree with themselves. That is not a property of the patterns. It is a property of how they were made: each came from a construction that returns a lettering, so a test looking for letters that contradict themselves has nothing to fire on. Reletter the same thirty-three and the failure is available at once — on one member, four of sixty redraws.

complexity · Typical instances 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

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.

rigid · Self-contact the bar is what the whole job costs if every attempt is stopped thereon the rhombille patch, read off 120 measured runsstop at 10051219% of runs finish by thenstop at 20053033% of runs finish by thenstop at 500105435% of runs finish by thenstop at 1000162442% of runs finish by thenstop at 2000263847% of runs finish by thenstop at 5000569749% of runs finish by thenstop at 100001060450% of runs finish by thenstop at 200001629160% of runs finish by thena run that never finished counts as above every cutoff, so the tail is read conservatively

Stopping is cheaper than finishing

A search whose cost varies by a factor of two hundred with nothing but the order of its guesses should not be waited out. Give up after a hundred steps, reseed and start again, and the whole job costs five hundred and twelve steps in expectation; run each attempt to twenty thousand and it costs sixteen thousand two hundred and ninety-one. Patience is thirty-two times more expensive than impatience.

complexity · Hardness of folding the bar is what the whole job costs if every attempt is stopped thereon the rhombille patch, read off 120 measured runsstop at 10051219% of runs finish by thenstop at 20053033% of runs finish by thenstop at 500105435% of runs finish by thenstop at 1000162442% of runs finish by thenstop at 2000263847% of runs finish by thenstop at 5000569749% of runs finish by thenstop at 100001060450% of runs finish by thenstop at 200001629160% of runs finish by thena run that never finished counts as above every cutoff, so the tail is read conservatively

The tail was named somewhere else

The search for a mountain-valley labelling of a tessellation patch costs eighty-four steps at best and does not finish at all two runs in five, and the cure is to stop and start again rather than to wait. None of that was discovered here. The distribution was described in the study of satisfiability solvers in the nineteen-nineties, the restart arithmetic is older still, and what a crease pattern contributes is one more instance.

history · Rediscovery the same 2×2 glued cell, searched under two rulesa cycle is a contradictiona cycle whose steps add to zero isand what the loops dothe square gridnothing, in 359 nodesevery loop travels (2 directions)the triangular gridnothing, in 12,143455 nodesevery loop travels (2 directions)the honeycombnothing, in 9,6191,043 nodesevery loop travels (3 directions)the elongated triangular tilingnothing, in 9,123162 nodesevery loop travels (5 directions)the rhombille tilingunfinished at 200,000unfinished at 200,000—“nothing, in n” is an exhausted search: a proof that the pattern has no consistent lettering, which is false

The cost of asking the wrong sheet

A test written for a sheet with an edge, run on a sheet without one, does not fail. It exhausts — proving, at three, thirty-five and three thousand four hundred and fifty-five nodes, that no lettering exists — and the letterings it proved impossible fold, on the collection's own machinery, at every size they were tried at.

complexity · Hardness of folding

Named alongside it

The objects these essays reach for when they reach for this one.

Necessary conditionLayer orderingFlat-foldabilitySearch costWorst-case analysisCrease patternEnumerationAssignmentFolded stateSearchTypical instancesThe big-little-big lemma

All concepts