Origami & Folding
what one sheet can do
Concept

Heuristic — where it appears

A rule for choosing that is not guaranteed to help. A search picks which crease to decide and which letter to try by such rules, and the better-informed rule is not reliably the cheaper one — branching on a pattern's own circuit structure buys nothing where a lettering exists and four orders of magnitude where none does.

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

2345678910-0.15-0.1-0.0500.050.10.15discsshortfall of the symmetric search14.6%1.7%0.0%-0.0%5.6%0.5%10.8%10.4%4.7%symmetry: mirror · both searches at 90 restartsneither number is a proved optimum — this compares two searches

When symmetry costs

Design software and designers both reach for symmetry, and for a good reason: it makes the search enormously easier. It is a heuristic and not a theorem, and how much it gives away can be measured — including the case where the optimum is symmetric about an axis nobody imposed.

design · Symmetry heavier means the crease lies on more independent circuits157 panels, 282 arcs, circuit rank 126; circuits run from 4 to 26 arcs

Which choice the cost lives in

A backtracking search takes two decisions at every step — which thing to decide, and what to decide about it. The literature is almost entirely about the first. On these crease patterns the whole of the cost was in the second, and the structural improvement everybody reaches for first makes matters worse on fifty-two patterns out of eighty-seven.

complexity · Search order the bar is what the whole job costs in expectation, in nodeson the rhombille patch, over the same 120 measured runs as the fixed cutoffsbest fixed, 100512chosen after seeing the runsunit 132226.30 times the best fixedunit 228545.58 times the best fixedunit 525424.97 times the best fixedunit 1021524.20 times the best fixedunit 2017623.44 times the best fixedunit 508481.66 times the best fixedunit 1005511.08 times the best fixedunit 2006381.25 times the best fixeda unit of one assumes nothing about the runs; every larger unit is a guess at their scale

What the hindsight was worth

The best restart cutoff for the one tessellation search with a heavy tail was read off a hundred and twenty measured runs, which nobody running the search could have done in advance. The universal schedule needs no such knowledge, and on the same runs it costs 3,222 nodes in expectation against 512 for the cutoff chosen by looking — a factor of 6.3, which is close to the base-two logarithm of that cutoff, as the theory of the schedule says it should be. A larger unit brings the schedule within a few per cent of the hindsight, and choosing the unit is choosing the scale the schedule was meant not to need.

history · Rediscovery the expected cost of the whole job under rules that learn from their own failures, in nodeson the rhombille patch, over the same 120 measured runs; the dark bar borrows its unit from other patchesbest fixed, 100512chosen after seeing the runsdouble after every failure1820at least 3.56 times the best fixeddouble after every failure, from sixteen1805at least 3.53 times the best fixedgrow by half after each failure1204at least 2.35 times the best fixeduniversal, unit of one32226.30 times the best fixeduniversal, unit from other patches8721.70 times the best fixeda rule that reads only its own failures cannot beat the best fixed cutoff, and cannot know which that is

A failure teaches a schedule nothing

The universal restart schedule costs 6.3 times the cutoff chosen by hindsight on the one folding search with a heavy tail, and the obvious repair is a schedule that learns its scale from the attempts it has already made. It cannot. A failed attempt costs exactly its cutoff and reports only that the run needed more, so every rule that chooses the next cutoff from its own failures writes down the same list whatever happens — a fixed schedule in disguise. On the measured runs, doubling after every failure costs at least 3.6 times the hindsight, and growing by half at least 2.4. What does come near is information from outside the run: the universal schedule given the longest search on four other patches as its unit costs 1.7 times the hindsight. The field that supplied the schedule reached the same conclusion, and answered it by watching runs from the inside.

history · Rediscovery each run, read at node 50, against how long it turned out to bethe top band is runs still unfinished at 20,000 nodes1234048121620times the loop test has refused the run so farnodes the run takes to finish, log₁₀finishes inside the cutofffinishes laternever finishesupright line: the refusalcount that restarts a runlevel line: the cutoff

A long run shows itself early

A restart schedule that learns only from failures was shown to be a fixed list in disguise, unable to beat the cutoff hindsight would choose. A run reports more than whether it has finished, though, and the search for a lettering of the rhombille patch already counts the one thing worth reading: how often its loop test has refused it. Read at node fifty, the count separates the runs. Of fifty runs refused eight times or more, one finishes within a hundred nodes; of seventy refused fewer times, twenty-two do. Restarting on that count costs 387 nodes in expectation against 483 for the best fixed cutoff — and chosen on half the runs and priced on the other half, 437 and 435 against 541 and 579, which on one half is cheaper than that half's own hindsight. The search literature's answer was right, and on a crease pattern it needs one number.

history · Rediscovery

Named alongside it

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

Search costRandomised algorithmRediscoveryRestartWorst-case analysisSearchAssignmentBacktrackingCircle packingConstraint propagationCycle spaceDesign technique

All concepts