Origami & Folding
what one sheet can do
Concept

Output-sensitive cost — where it appears

Cost measured against the size of the answer rather than the size of the question. Listing every folded state of a strip is expensive because there are many of them, which is a different kind of hardness from deciding.

Named by 2 essays across one field — each of them below, with the objects they name alongside it.

mapflat foldingsand what it took2 × 284 cells, computed here2 × 3606 cells, computed here2 × 43208 cells, computed here3 × 31,3689 cells, computed here2 × 51,9800.6 s3 × 415,55254 s4 × 4300,608not reached herethe 1 × n case is the strip, and it is the only row of this table with a fast methodnobody has a formula for any entry, and nobody has proved there is none

The answer is bigger than the question

A twelve-square strip of stamps is twelve numbers of input and 146,376 objects of output. No algorithm writes that faster than it can be written, so 'efficient' has to be measured against the answer rather than against the question — and in folding that is the normal case.

complexity · Hardness of folding 4681012010203040sides of the polygoncreasescreases in the patternperpendicularsskeleton arcsa 12-sided outline needs 36 creases and one skeleton nodea convex outline is the cheap casea reflex corner splits the shrinking front, and this solver refuses those rather than guessing

What universality costs

The fold-and-cut theorem says any straight-line drawing can be flattened onto a single line. It says nothing about how much crease pattern that takes, and the amount is a measurable quantity — computed here by running the construction rather than by estimating it.

complexity · Flat-foldability

Named alongside it

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

Combinatorial explosionCompletenessThe counting problemEnumerationThe fold-and-cut theoremMap foldingReductionStamp foldingStraight skeletonUniversality

All concepts