Origami & Folding
what one sheet can do
Concept

Optimisation — where it appears

Searching for the best member of a family rather than deriving it. Most packing questions in this subject are settled by search, so the answers quoted are the best anything has found rather than proved optima, and comparisons need equal effort on both sides.

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

leglegarmarmheadthe checkclosest approach 0.0000no overlap — the packing is validcircles use 71% of the sheetthe rest becomes the bodyefficiency is how much of thesquare the circles can claim,and it is an open problemthe dashed skeleton is the subject; the circles are what it costs

Packing is the hard part

Once a subject is a set of circles, designing the model is fitting them into a square. That step has no general algorithm, no known optimum, and it is where every remaining difficulty in origami design now sits.

design · Circle packing 2 discs53.9%r = 0.29293 discs61.0%r = 0.25434 discs78.5%r = 0.25005 discs67.3%r = 0.20716 discs66.3%r = 0.18767 discs66.9%r = 0.17448 discs72.8%r = 0.17029 discs78.5%r = 0.1667hexagonal density 90.69%every bar is the best a seeded search found, not a proved optimum —which is the honest state of the problem for all but the first few values of n

How much paper is wasted

The efficiency of a design is the fraction of the sheet its flaps can claim, and for almost every number of flaps nobody knows the best possible value. The bars in these figures are the best a search could find, which is not the same thing.

design · Circle packing 6 creases, 7 segments, assignment MVMVMVDoes it fold flat?at most 5,040 orderings, and it may stop earlyyesas far as the first legal oneHow many ways?every one of them, because the last is as likely as the first15,040 orderingsWhat are they?the same search, paying a second time for what it keeps1 stackings, written out5,040 orderings, and the answer as wellCan a machine make it?a different search, over sequences of folds rather than over stackingsno1,275 statesthe four are not four difficulties of one problem — they are four problemsthe cost is work rather than time — a clock reading would differ on every build

Four questions about one sheet

Deciding, counting, listing and optimising are not four difficulties of one problem. They are four problems, and folding is the subject that proves it: a ruled map is trivial to decide and unsolved to count, while a general crease pattern is the other way round.

complexity · Hardness of folding discsfoundproved bestshort by20.292880.292890.00%30.254310.254330.01%40.250000.25000matched50.207050.207110.03%60.187580.187680.05%70.174360.174460.06%80.170220.170540.19%90.166670.16667matchedworst shortfall 0.19% of the radius, at 8 discsthe search never consults the published values, so the comparison measures the searchbeyond nine discs there is nothing to compare against, because nothing has been proved

Getting close instead of getting it right

When the best answer is out of reach the question stops being what it is and becomes how much is lost. For packing discs into a square the loss is measurable: a seeded search in this repository comes within a fifth of a percent of the best radius anybody has proved, and proves nothing.

complexity · Circle packing quadrilateralconvexmolecule builtpentagonconvexmolecule builtL, one reflex cornerone reflex cornerconstruction refusedthe polygon admits a shrinkingdart, one reflex cornerone reflex cornerconstruction refusedthe polygon admits a shrinkinga convex polygon shrinks inward and stays a polygon; a reflex corner is a wall the shrink runs intoso a non-convex region is split into convex pieces first, and choosing the split is a searchwhich is where a construction that always works hands the difficulty to whatever comes before it

The molecule that does not exist

The universal molecule fills any convex polygon, always, which is what makes it the part of the tree method with no special cases. Hand it a reflex corner and it does not produce a worse pattern — it produces nothing, and the difficulty moves backwards to whoever chose the polygons.

design · Molecules flapsfree search4×4 grid8×8 grid30.25430.2500 −1.7%0.2500 −1.7%40.25000.2500 −0.0%0.2500 −0.0%50.20710.1768 −14.6%0.1768 −14.6%60.18760.1250 −33.4%0.1398 −25.5%the 6-flap case on the finest lattice here is one of 3.25e+8 arrangements, and the bound settles all of themthe free optimum is unknown for most of these counts and the lattice optimum is known for all of thema finer lattice costs less and asks for more creases, which is the trade a designer actually makes

What the grid settles

Box pleating is usually defended as a trade: give up efficiency, buy creases that land where they should. There is a second thing it buys and nobody quotes it — on a lattice the best possible packing is a finite question with an answer, while off the lattice nobody knows the best packing of six circles in a square and probably never will.

design · Box pleating 42:3:4:363:4:6:583:4:6:5125:7:11:8165:7:11:8248:11:17:13each limb roundedthe best whole numbershow wrong the worst limb isgrid units across the longest limbthe numbers under the axis are the best whole-number limbs at that resolution

Spelling a tree on a grid

Box pleating asks every limb of a design to be a whole number of grid squares, which sounds like rounding and is not. Rounding each limb to its own nearest whole number is one way to choose the numbers, and at most resolutions it is not the best way — the best whole-number version of a subject is often a coarser one, with fewer squares and a shape twice as close.

design · Box pleating 0.287267creases in the moleculewhere the corner sits7 creases6 creasesat the marked shape three of the polygon's edges vanish at the same instant, and either side of it they vanish one at a time

The skeleton changes its mind

The universal molecule fills any convex polygon, always, which is what makes it the part of the tree method with no special cases. It does not fill it continuously. Slide one corner along its edge and the number of creases in the molecule sits at six, jumps, and sits at seven — so two designs a hairsbreadth apart have crease patterns that are not small variations on one another.

design · Molecules 6 flaps at radius 0.1875883 contact graphs among the runs that agree about itone run5 contacts · 5 against the paper's edgeanother run4 contacts · 5 against the paper's edge

Two packings, one radius

A packing search reports a number, and the number is not the design. What a crease pattern is built from is the graph of which discs touch which — and at five and six flaps, runs of the same search that agree about the best radius to four decimal places come back with contact graphs that are provably not the same graph. The answer an optimiser gives has not determined the pattern it is supposed to have found.

design · Circle packing

Named alongside it

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

Tree methodCircle packingBox pleatingThe decision problemDesign techniqueEnumerationGridNP-hardRiverStraight skeletonAxial polygonBoundary effect

All concepts