One straight cut

Most of the results in this field are about what cannot be done. Flat-foldability is intractable in general, a sheet cannot become a sphere, a compass cannot reach a heptagon. It makes a change to meet a theorem that says yes to a question that sounds impossible.

Fold a sheet of paper. Make one straight cut. Unfold. The theorem says that the piece released can be any shape made of straight line segments — a polygon, several polygons, a stick figure, every letter of the alphabet at once — and that a folding always exists.

What the cut has to achieve #

Start from the end and work backwards, because the requirement is easier to see than the construction.

A single straight cut removes everything along one line of the folded sheet — which makes this, unusually for a site whose rule is that the sheet is never cut, a theorem about cutting. So for the cut to release a given outline, every point of that outline must land on that line, and no other point of the sheet may.

The first half is the demanding one: the whole outline, however long and however many corners it has, must be brought onto a single straight line by folding alone. Folding is a sequence of reflections, and reflections preserve distance — so bringing a point onto the cut line means the folded sheet has arranged that point at exactly the right place.

Restated once more: the folded sheet must be arranged so that the outline lies along a single line. Everything below is a construction that does that.

The cut line is not a crease #

One point of vocabulary needs settling before the construction, because the figures would otherwise be misread.

The outline drawn in green on every figure here is not a fold. It is the line the scissors follow after the sheet has been folded — or, seen on the flat sheet, the set of points that will end up under the blade. Nothing is creased along it.

That is why it is drawn in the construction colour rather than in mountain-red or valley-blue. Those two are reserved on this site for crease assignments and are used for nothing else, and a cut line coloured like a crease would be asserting that the paper bends where in fact it is severed. The distinction is not pedantry: a folder handed this pattern creases along the red and blue lines, folds the sheet flat, and then cuts along a straight line that has no counterpart in the flat pattern at all.

There is a second thing the cut line is not, and it catches people out. It is not the boundary of the sheet. The sheet is the square; the outline sits inside it; and the creases run from the outline out to the square’s edge in the full construction. The figures here draw the creases within the outline only, which is the part the skeleton determines.

Shrinking, which is the whole idea #

The construction has one idea in it, and the idea is a process rather than a formula.

Take the outline and shrink it. Move every edge inward, parallel to itself, at the same speed. Each corner slides along its own angle bisector because that is the locus of points equidistant from the two edges meeting there. As the shrinking proceeds, edges get shorter; eventually one of them vanishes, and at that moment its two neighbours become adjacent and the shrinking continues with one edge fewer.

The traces the corners leave behind are the straight skeleton. The moments when edges vanish are its nodes. For a triangle the shrinking closes to a point and the skeleton is three segments meeting at the incentre; for a long rectangle it closes to a segment and the skeleton has four bisector arcs and a spine.

Now the property that makes it work. Every point of the skeleton was reached by the shrinking at some time, and the shrinking moved every edge at the same speed — so a point of the skeleton at time t is exactly distance t from each of the edges that were still alive around it. Points of the skeleton are equidistant from the edges that define them.

That equidistance is the reason one fold can serve several edges at once. Fold along a skeleton arc and the two edges either side of it, being equally far from the fold, land on top of one another.

The second half, which is the perpendiculars #

The skeleton alone does not finish the job, and it is worth being clear about what is missing.

Folding along the skeleton brings the edges together in pairs and stacks them — but it stacks them at their own angles, not flat along one line. An edge folded onto its neighbour is still an edge in whatever direction it was pointing.

So a second family of creases is needed: from each skeleton node, a perpendicular dropped onto each edge that defined it. Folding along those flattens each edge into the line, and because the node is equidistant from all of its edges the perpendiculars are all the same length and reach the line together.

Skeleton plus perpendiculars, then, is the whole crease pattern. The skeleton brings edges into coincidence with each other; the perpendiculars bring the result down onto the cut line. Neither works alone.

Which theorem was checked, and how #

Three separate claims are made by these figures and each is verified rather than drawn.

The skeleton is computed, not sketched. The generator implements the shrinking literally: every edge is carried by its inward normal, the offset polygon’s corners are the intersections of the offset lines, the length of each edge is affine in the offset distance so its collapse time is solved for exactly, and the shape is shrunk event by event until nothing is left. No bisectors are drawn by hand.

The equidistance is asserted. For every node, the distance to each edge that defined it is measured and compared. If the largest and smallest differ by more than a part in ten million the generator throws, because the fold that is supposed to serve both edges would not exist. The number printed beside each figure is that discrepancy, and it sits at the level of floating-point rounding.

The assignment is found rather than stated. The skeleton arcs and the perpendiculars alternate around a node, so the obvious colouring is one letter for the arcs and the other for the perpendiculars. At a node of degree six that is three and three — and Maekawa forbids a tie. The generator tests that colouring explicitly, records that it fails, and searches for one that does not.

What the figures cannot show is the theorem. They show that this construction works for these outlines; the claim that it works for every straight-line drawing is a proof, and the proof needs cases the pictures here do not contain.

The restriction these figures carry #

The skeleton implemented here handles convex outlines only, and the reason is worth stating because it is where the real difficulty of the algorithm lives.

Shrinking a convex shape produces only one kind of event: an edge reaching zero length. Shrinking a non-convex shape produces a second kind. A reflex corner — one that points inward — moves outward as the shape shrinks, and it can run into a distant edge and split the shrinking region into two. Handling those split events correctly, in the right order, with the right bookkeeping, is what makes straight-skeleton implementations long.

So the generator refuses a reflex outline rather than producing a plausible-looking wrong answer. That is the right failure: an outline with a notch in it has a genuine skeleton, this code does not compute it, and drawing something approximately right would assert a construction that does not fold.

The theorem itself has no such restriction. It covers any plane graph of straight segments — including disconnected ones, including ones with corners of every kind — and the published constructions handle them.

Where the model stops #

The pattern folds flat, and that is checked. The creases here satisfy every vertex condition the site tests, which is necessary and, as always, not sufficient.

Zero thickness, and it matters more here. The folded state for a shape of any complexity has a great many layers, and the cut has to go through all of them. A real sheet of anything reaches a thickness at which scissors stop, which is why the impressive demonstrations use thin paper and simple outlines.

The fold sequence is not the crease pattern. Knowing the pattern is not knowing how to bring the sheet into that state, which is the layer-ordering problem again. For a fold-and-cut pattern the ordering is constrained but not determined, and finding a physically achievable sequence is a separate exercise.

Only the outline lands on the line. Everything else must land off it, and for some shapes the margin is small. The construction guarantees the first condition; the second is checked in the published proofs and is not visible in a figure.

A second method exists and is different. The construction above is the straight-skeleton method. There is also a disk-packing method, which produces different creases for the same outline and has better theoretical guarantees. Both are constructive; neither is canonical.

Nothing here is optimal. The number of creases these patterns use is not the smallest possible, and minimising it is an open problem.

Convexity is this implementation’s limit, not the theorem’s. The published constructions handle any straight-line figure; the honest statement of a restriction is that it belongs to the code rather than to the result.

The outside of the shape needs its own skeleton. The construction shown covers the inside of the outline. A full fold-and-cut pattern also treats the region between the outline and the edge of the sheet, which has its own skeleton and its own perpendiculars. The figures here stop at the outline, which is the half where the idea lives.

What the folded state looks like #

The crease pattern is drawable and the folded state mostly is not, and it is worth saying what is being left out.

Fold a triangle’s pattern and the result is a narrow wedge of paper, several layers thick, with all three edges of the triangle lying exactly along one edge of the wedge. Fold a five-pointed star’s and the result is a thin sliver with ten edges stacked along its boundary. The folded object is not interesting to look at; it is a compressed bundle whose only remarkable feature is that one straight line through it meets the whole outline.

That is why the demonstrations are always done as a performance rather than as a diagram. The crease pattern is legible, the cut is dramatic, and the state in between is a crumpled-looking wad that reveals nothing. Every published account jumps from one to the other, and the reason is that the middle step is genuinely not a picture.

It also means the number of layers grows quickly. Each edge of the outline contributes at least one layer at the cut, so a shape with thirty segments is thirty layers deep along the blade before any of the folding overhead is counted. Paper thin enough to cut in thirty layers is thin enough to tear, which is the practical limit on how elaborate the demonstration gets.

Every letter at once #

The theorem’s strongest form is the one that makes it sound absurd, and it is worth stating because it follows for free.

The input may be any plane graph of straight segments. It need not be connected, it need not be a single closed shape, and it need not be simple. So the whole alphabet, written out in straight strokes and scattered across a sheet, is a legal input — and there is a folding of that sheet, and one cut, that releases all twenty-six letters simultaneously.

Nothing in the construction cares. The skeleton of a disconnected figure is a disconnected skeleton, the perpendiculars are dropped as before, and the pieces are brought onto the same line by folds that pass between them.

That generality is what separates the theorem from the tricks that preceded it. Houdini’s star and Loe’s collection were recipes for particular shapes, each found by somebody good at folding. The theorem says the recipe always exists and gives an algorithm for it, and the difference between “somebody found one for a star” and “one exists for every straight-line figure” is exactly the difference between a puzzle and a result.

The surprise: it is a positive result in a hard neighbourhood #

The most interesting thing about fold-and-cut is where it sits.

Deciding whether an arbitrary crease pattern folds flat is NP-hard. Deciding whether a given assignment has a consistent layer order is NP-hard. The subject is intractable in almost every direction anybody has looked — and yet here is a construction that takes an arbitrary input, does something that sounds much harder, and runs in polynomial time.

The resolution is that fold-and-cut is not the hard problem in disguise. The hard problem is deciding whether a given pattern folds; this is constructing a pattern with a property, and the construction gets to choose the pattern. Being handed the freedom to design is worth a great deal, which is the same reason a designer never meets the intractable cases — designed patterns are built up rather than discovered, and their foldability comes with the construction.

That distinction is a general one and it is worth carrying elsewhere. Verification is not the same problem as synthesis, and a hardness result about one says nothing directly about the other.

It is also the reason this essay belongs to the same ladder as the hardness result rather than to a different one. Both are statements about what can be decided about a crease pattern; they point in opposite directions, and they do not conflict, because they are about opposite directions of the same arrow.

Who found it, and when #

The theorem is recent; the trick is very old.

Fold-and-cut appears as a puzzle in a Japanese book of 1721 and as a set of published cut-outs in nineteenth-century magazines. Harry Houdini included a five-pointed star made this way in a book of 1922, and Gerald Loe published a collection of them in 1955 — all of these being particular shapes with particular folding recipes, and none of them a general claim.

The general theorem was proved by Erik Demaine, Martin Demaine and Anna Lubiw in 1998: every plane graph of straight-line segments can be folded flat so the graph lands on one line. Marshall Bern, Erik Demaine, David Eppstein and Barry Hayes gave the disk-packing construction shortly afterwards, which is a different proof of the same statement with better bounds.

It is worth noticing what the 1998 proof added to a trick that already worked. Houdini could make a star; nobody could make an arbitrary figure, and nobody knew whether it was possible. A construction that always works is a different kind of object from a construction that works — the same distinction that separates an assignment somebody found from an algorithm that finds one.

The straight skeleton itself came from somewhere else again. Oswin Aichholzer and colleagues introduced it in 1995 for roof design — the skeleton of a building’s outline is where the ridges of a hipped roof go — and its arrival in folding was a borrowing. The connection makes sense once stated: a roof is the surface swept by edges moving inward at a constant rate, and so is a shrinking polygon.

The ladder from here #

Later rungs against this anchor: the disk-packing construction, and why it gives better bounds than the skeleton method. Split events, and what makes a non-convex skeleton hard to compute. The proof that nothing but the outline lands on the cut line. Fold-and-cut with several cuts, and what that buys. The three-dimensional analogue, which is about cutting a solid with a plane. And the minimisation question — the fewest creases for a given outline — which is open and does not look easy.

The theorem is a rarity in this subject: a question that sounds impossible, an answer of yes, and a construction short enough to draw.