Origami & Folding
what one sheet can do
What it costs to know

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.

Assumes One straight cut.

18 min read 6 figures The pattern is the objectOne sheet, no cuts

Any drawing made of straight segments can be folded flat so that the whole drawing lands on one line, and a single cut releases it. That is the fold-and-cut theorem, and the word doing the work is any.

A universality theorem of that form is a promise about existence and is silent about size. It does not say how many creases the folding takes, how the count grows with the drawing, or whether the pattern is something a person could execute. Those are separate questions with separate answers, and they are answerable — by running the construction and counting what comes out.

What the fold-and-cut construction costsThe number of creases the fold-and-cut construction produces for a regular polygon, against the number of sides. Everything is computed: the skeleton by shrinking the outline, the perpendiculars from the nodes it produces, and the count by counting. The growth is linear here because a regular polygon's skeleton is a single point, which is the easiest case there is.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
Fig. 1 The creases the fold-and-cut construction produces for a regular polygon, against the number of sides. Everything here is computed: the skeleton by shrinking the outline, the perpendiculars from the nodes that shrinking produced, and the count by counting. The figure refuses to draw if a regular polygon’s skeleton ever comes out as more than a single node.

The construction, and what it emits

The construction itself has two halves and each contributes creases.

The straight skeleton is what the outline traces as it shrinks inward at uniform speed. Its arcs are creases, and where the shrinking front collapses, a node forms. The skeleton is computed here by actually offsetting the edges and solving for the collapse times exactly, rather than by drawing angle bisectors that look about right.

The perpendiculars run from each skeleton node to each edge that defined it. They are the second half and they are the half that does the flattening: the skeleton alone folds the shape, and the perpendiculars are what carry the boundary down onto the line.

So the output is the outline, plus the skeleton arcs, plus the perpendiculars. For a regular polygon that is n boundary edges, n arcs meeting at the centre, and n perpendiculars — three creases per side, and the figure above is a straight line because a regular polygon is the easiest case the theorem has.

One straight cut: the pentagonAn outline, the straight skeleton computed by shrinking it, and the perpendiculars dropped from each skeleton node onto the edges that formed it. Folding along these carries every edge of the outline onto a single line, so one straight cut releases the shape. The mountain-and-valley assignment is found by search, because the obvious one fails Maekawa.the cut line5 straight edgesthe pattern5 skeleton arcs5 perpendiculars1 interior vertexassignments that fold420 of 102410 creases in allarcs one way, perpendicularsthe other: fails Maekawaequidistance off by 5.6e-17mountainvalleyevery node sits the same distance from each edge that formed it,which is why one fold can carry several edges onto the line at once
Fold and cut — pentagon — sheet 150×150 mm — 4 mountain, 6 valley, 434.16 mm of crease
Fig. 2 The pattern for a regular pentagon, drawn from the construction rather than described. Five arcs to the centre, five perpendiculars to the edges, and the outline. The assignment is found by search, because the obvious colouring — one letter for the arcs and the other for the perpendiculars — is a tie at a node of even degree, and Maekawa never allows a tie.

Why the easy case is worth measuring anyway

A linear count on the easiest inputs might look like a figure that proves nothing, and it earns its place for two reasons.

The first is that it establishes a floor. Three creases per side is what the construction costs when everything goes right; nothing about a more complicated outline reduces it. Any statement about the cost of fold-and-cut has to start from at least this much.

The second is that the figure is a test. A regular polygon’s skeleton is a single node at the centre, and the generator throws if the solver ever reports more than one. That is a real assertion about a numerical procedure — the collapse times of n edges shrinking at equal speed are all equal, and a solver with a tolerance problem would split that single node into a cluster of nearly-coincident ones and quietly emit a different pattern.

A figure whose subject is a count is worth very little without an assertion about what was counted. The skeleton solver here merges nodes within 10⁻⁹ and the equidistance of every node from every edge that defined it is checked before anything is drawn.

Where it stops being linear

Regular polygons are the good case and the construction’s real cost is not linear, for a reason the solver here makes unavoidable: it refuses non-convex outlines.

The skeleton routine throws when the outline has a reflex corner. That is not a limitation to be apologised for; it is an accurate report of what the implementation does and does not handle. A reflex corner produces a split event, where the shrinking front reaches a wall and the shape divides into two, and handling those correctly is a substantially harder algorithm than offsetting convex edges.

The cost consequence is direct. A convex polygon’s skeleton has at most n − 2 nodes. A non-convex one can have many more, because every split creates new fronts that go on to collapse among themselves, and the number of skeleton events — hence the number of creases — grows faster than the number of edges of the drawing.

So the honest statement of the cost is: linear on convex outlines, and superlinear in general by an amount not measured here, because it declines to compute the cases where it would show up.

One straight cut: the houseAn outline, the straight skeleton computed by shrinking it, and the perpendiculars dropped from each skeleton node onto the edges that formed it. Folding along these carries every edge of the outline onto a single line, so one straight cut releases the shape. The mountain-and-valley assignment is found by search, because the obvious one fails Maekawa.the cut line5 straight edgesthe pattern7 skeleton arcs9 perpendiculars3 interior vertexesassignments that foldfound by search16 creases in allarcs one way, perpendicularsthe other: fails Maekawaequidistance off by 1.7e-16mountainvalleyevery node sits the same distance from each edge that formed it,which is why one fold can carry several edges onto the line at once
Fold and cut — house — sheet 150×150 mm — 5 mountain, 11 valley, 619.17 mm of crease
Fig. 3 The most complicated outline this solver will accept: five edges, all convex, and one of them at an angle that puts the skeleton node off centre. A house shape with the roof pushed inward would have a reflex corner, and the solver would throw rather than guess at where the front splits.

The generic convex case is twice the regular one

The floor is three creases per side and the next case up can be derived rather than measured, which is worth doing because it says how special the regular polygon is.

A convex polygon of nn sides has a skeleton that is a tree with the nn corners as its leaves. In the regular case all the arcs collapse to one node in the middle. In the generic case, where no two collapse events coincide, the internal nodes are all of degree three and there are n−2n-2 of them — so the tree has n+(n−2)−1=2n−3n + (n-2) - 1 = 2n-3 arcs.

The perpendiculars follow from the same count. Each internal node drops one perpendicular to each edge that defined it, and a degree-three node was defined by three, so there are 3(n−2)=3n−63(n-2) = 3n-6 of them.

Adding the boundary:

n+(2n−3)+(3n−6)=6n−9n + (2n-3) + (3n-6) = 6n - 9

against 3n3n for the regular polygon. A generic convex outline costs about twice what a regular one of the same number of sides costs, and the pentagon is the smallest case where the gap is visible: fifteen creases regular, twenty-one generic.

Which half grows

The split between the two halves of the construction is worth reading, because it does not stay even.

For a regular polygon the arcs and the perpendiculars are equal in number, nn apiece. For a generic convex one they are 2n−32n-3 and 3n−63n-6: the perpendiculars outnumber the arcs, and their share rises from a third of the pattern to a half.

So the half that does the flattening is the half that grows, and that is the half whose creases all have to close simultaneously. A count of creases understates the difference, because the extra creases are not spread evenly — they radiate from the skeleton’s internal nodes, which is exactly where the paper is already densest.

The regular polygon’s single central node is therefore not merely the cheapest case; it is the case with the fewest places for creases to concentrate. Every degeneracy the construction can have — coincident collapse times, edges of equal length, a symmetry that merges nodes — reduces both the count and the crowding at once, and a shape drawn to look tidy is a shape whose skeleton has been quietly simplified.

None of that is measured here, since the solver stops at convex outlines and the interesting growth is past them. It is derivable, it agrees with the regular case the figure does measure, and it sets the next thing worth counting.

Counting a construction is a habit worth generalising

Fold-and-cut is one construction and the question it prompts is general: for any procedure that turns a specification into a crease pattern, how much pattern comes out?

This site runs several such procedures and the answers are not alike. A circle packing turned into a crease pattern emits ridges and hinges whose count follows from the packing’s contacts. A box-pleated design on a grid emits creases at grid resolution, so its count is set by the grid rather than by the shape. The universal molecule emits a pattern whose complexity depends on how many sides the polygon has and on nothing else.

One straight cut: the ellAn outline, the straight skeleton computed by shrinking it, and the perpendiculars dropped from each skeleton node onto the edges that formed it. Folding along these carries every edge of the outline onto a single line, so one straight cut releases the shape. The mountain-and-valley assignment is found by search, because the obvious one fails Maekawa.the cut line6 straight edgesthe pattern8 skeleton arcs8 perpendiculars3 interior vertexesassignments that foldfound by search16 creases in allarcs one way, perpendicularsthe other: fails Maekawaequidistance off by 5.6e-17mountainvalleyevery node sits the same distance from each edge that formed it,which is why one fold can carry several edges onto the line at once
Fold and cut — ell — sheet 150×150 mm — 6 mountain, 10 valley, 460.92 mm of crease
Fig. 4 Counting a construction is a habit worth generalising, and here is the same count on a shape with a reflex corner: the L, its skeleton and its perpendiculars. What comes out is a crease for every event the shrinking outline goes through.

That last observation is the useful one. Two constructions can realise the same specification and emit patterns of very different sizes, and nothing in either theorem mentions it. Choosing between them is engineering, and the quantity being engineered is invisible in the mathematics.

Universality is not the same as practicality

Three universality results sit near each other in this subject and all three have the same shape and the same silence.

Fold-and-cut: any straight-line drawing, one cut. Universal.

Any polyhedral surface can be folded from a sufficiently large square. Universal, and the “sufficiently large” is doing an enormous amount of work — the scale factor between the square and the surface is where all the practical content lives.

Any tree can be realised as a uniaxial base, by packing circles for its leaves. Universal in principle, and what a designer wants is not existence but a base whose paper is not mostly wasted.

In every case the theorem’s contribution is to rule out a class of impossibility arguments, and the interesting work begins afterwards. That is not a criticism of universality theorems; it is a description of what they are for. A universality result tells nobody how to do anything. It tells everybody to stop looking for a reason it cannot be done.

The three also fail to be practical in three different ways, which is worth separating. Fold-and-cut’s pattern is the right size and the wrong shape for a machine — a few dozen creases that must all close at once. The polyhedron result’s pattern is the right shape and catastrophically the wrong size, because the scale factor grows with the surface’s detail. And the tree method’s pattern is both right, and arrived at by an optimisation nobody can solve exactly. Three universality theorems, three distinct reasons the promise is not a recipe.

One straight cut: the starAn outline, the straight skeleton computed by shrinking it, and the perpendiculars dropped from each skeleton node onto the edges that formed it. Folding along these carries every edge of the outline onto a single line, so one straight cut releases the shape. The mountain-and-valley assignment is found by search, because the obvious one fails Maekawa.the cut line10 straight edgesthe pattern10 skeleton arcs0 perpendiculars1 interior vertexassignments that fold420 of 102410 creases in allarcs one way, perpendicularsthe other: fails Maekawaequidistance off by 1.9e-16mountainvalleyevery node sits the same distance from each edge that formed it,which is why one fold can carry several edges onto the line at once
Fold and cut — star — sheet 150×150 mm — 4 mountain, 6 valley, 363.75 mm of crease
Fig. 5 Universality is not the same as practicality, and the star is where the difference shows: the same construction on a five-pointed outline, with every crease it produces. The theorem promises one cut for any shape; this is the pattern that promise arrives as.

The count and the folding are different quantities

There is one more silence worth naming, and it is the one that separates this essay from a purely combinatorial exercise.

Counting creases counts drawing. It does not count the difficulty of executing the fold, and those come apart badly. A fold-and-cut pattern for a modest polygon has a few dozen creases, and folding it means collapsing all of them at once — the pattern has no sequence of simple folds that reaches it, because the skeleton arcs and perpendiculars all have to close together.

That connects directly to the machine ladder: fold-and-cut patterns are precisely the kind that fold flat and are not reachable by a restricted machine. A theorem guaranteeing a folded state exists guarantees nothing about a route to it, and here the route is known to be awkward for anybody without hands.

So the cost of universality has at least three components and this essay measures one. The number of creases is countable. The difficulty of the collapse is not measured here. The scale factor — how large a square is needed — does not arise for fold-and-cut and dominates the polyhedron result.

The assignment, which the construction does not supply

There is a part of the cost that is not a crease count at all, and fold-and-cut is where this site first ran into it.

The construction gives the crease lines. It does not give the mountain-and-valley assignment, and the obvious guess is wrong: at a skeleton node the arcs and the perpendiculars alternate and are equal in number, so colouring one family mountain and the other valley gives a tie — and Maekawa never allows a tie. The assignment has to be found by search.

One straight cut: the triangleAn outline, the straight skeleton computed by shrinking it, and the perpendiculars dropped from each skeleton node onto the edges that formed it. Folding along these carries every edge of the outline onto a single line, so one straight cut releases the shape. The mountain-and-valley assignment is found by search, because the obvious one fails Maekawa.the cut line3 straight edgesthe pattern3 skeleton arcs3 perpendiculars1 interior vertexassignments that fold30 of 646 creases in allarcs one way, perpendicularsthe other: fails Maekawaequidistance off by 1.9e-16mountainvalleyevery node sits the same distance from each edge that formed it,which is why one fold can carry several edges onto the line at once
Fold and cut — triangle — sheet 150×150 mm — 2 mountain, 4 valley, 257.98 mm of crease
Fig. 6 The simplest fold-and-cut pattern this site draws, with the assignment found rather than stated. The naive colouring is tested and reported as failing, in the same spirit as the preliminary base — an assignment nobody checked is an assertion nobody checked.

So a universality theorem can be silent in two directions at once. It is silent about how much pattern, which this essay measures. And it can be silent about whether the pattern it describes is fully specified — here the lines are determined and the letters are not, and finding the letters is a search whose cost grows with the pattern the construction just emitted.

That compounding is worth noticing. The construction’s output is the search’s input, so a cheap construction that emits a large pattern hands an expensive problem to whatever comes next.

What the figure cannot show

The figure counts creases and says nothing about where they are, and the distribution matters more than the count for anything anybody would fold.

Fold-and-cut patterns concentrate creases near skeleton nodes, and a node where many edges meet has many perpendiculars radiating from it. So the paper is nearly blank in some regions and dense in others, and the density is what decides whether the pattern is foldable in practice — layers accumulate where creases do, and a dense region is a thick one.

A count also hides the lengths. Total crease length is arguably the better measure for a manufacturing process, since a scoring machine pays per millimetre rather than per line, and it is computed here for the printable patterns, without having been plotted against outline complexity.

And the figure only shows regular polygons, so it shows the construction’s best behaviour and nothing about its worst. That is stated on the figure’s own face rather than left for a reader to infer.

There is one more absence, and it is the one this site is most careful about elsewhere. The figure counts creases in the pattern; it does not count layers in the folded state, and the folded state is where a fold-and-cut collapse becomes difficult. Every part of the outline ends up on one line, so every part of the paper ends up stacked along it, and the depth of that stack is what a person folding one actually fights. Counting it means solving the layer ordering, which is the problem this site does not solve in two dimensions.

A theorem’s silence is not a defect

It is worth resisting the reading that these theorems are somehow incomplete for not bounding their own output. They are not, and understanding why sharpens what a cost measurement is for.

A universality theorem’s job is to settle a question that would otherwise absorb effort indefinitely. Before 1998 it was reasonable to wonder whether some shape existed that no folding could flatten onto a line, and reasonable to look for one. After 1998 that search is closed, and everybody’s attention moves to the constructions and their sizes. The theorem converts an open-ended question into an engineering one, and that is exactly the service it was meant to provide.

The same is true of the results in the other direction. NP-hardness closes the search for a fast general algorithm and redirects attention to restricted families where fast algorithms do exist. Both kinds of theorem work by ruling out a class of ambitions, and both leave the quantitative work untouched.

What is a defect is treating the theorem as though it had answered the quantitative question too. A pattern with four hundred creases and a pattern with forty both satisfy “a folding exists”, and only one of them is a thing anybody folds.

The idealisation, named

The construction assumes the drawing is made of straight segments and that the paper is large enough to contain the whole skeleton with room for the perpendiculars.

The second assumption is not free. The skeleton of a shape lives inside it, but the perpendiculars can run to the edges of the shape and the folding needs paper beyond the drawing to fold into. How much beyond is a question about the shape, not a constant, and a fold-and-cut pattern presented on a sheet only slightly larger than its outline is presenting a construction that will not close.

The first assumption is what makes the theorem finite. A curved outline has no straight skeleton in this sense, and approximating a curve by segments turns one smooth boundary into a great many edges — at which point the crease count is a statement about the approximation rather than about the shape. That is the ordinary trap of discretising a curve, and it is worth naming because a fold-and-cut pattern for a circle is a thing people ask for.

Who proved this, and when

The fold-and-cut theorem was proved by Erik Demaine, Martin Demaine and Anna Lubiw in 1998, with an independent proof by Marshall Bern, Erik Demaine, David Eppstein and Barry Hayes shortly after using a different construction. The problem is much older as a puzzle: Harry Houdini published a five-pointed-star fold-and-cut in 1922, and versions of the trick go back further still.

The straight skeleton as a computational object is due to Oswin Aichholzer, Franz Aurenhammer, David Alberts and Bernd Gärtner, in 1995. The refusal to handle split events here is a deliberate scope decision recorded in the solver, and the essay says so rather than letting a green build imply a completeness that is not there.

Where the ladder goes next

Counting what a construction emits is one way to put a number on a theorem’s silence. The other is to ask how good an answer is, when the best answer is out of reach: the packing that a design rests on can be measured against the best packing known, the gap is a number, and it is the only place on this site where an optimisation is scored rather than merely performed.

Where this goes next

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. the cut line3 straight edgesthe pattern3 skeleton arcs3 perpendiculars1 interior vertexassignments that fold30 of 646 creases in allarcs one way, perpendicularsthe other: fails Maekawaequidistance off by 1.9e-16mountainvalleyevery node sits the same distance from each edge that formed it,which is why one fold can carry several edges onto the line at once One straight cut Any drawing made of straight lines can be folded so that the whole drawing lands on a single line, and one cut releases it. The construction is a shrinking process, and it explains itself the moment the shrinking is drawn. 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.

Named alongside this one

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

What links here

Every essay whose body links to this one.

The objects this essay names

Each one links to every other essay that touches it.

CompletenessThe fold-and-cut theoremOutput-sensitive costReductionStraight skeletonUniversality