The molecule that does not exist

The universal molecule is the piece of the tree method that makes the whole thing a method rather than a collection of tricks. Once a packing has decided where the flaps go, the leftover regions between them need crease patterns of their own, and the molecule supplies one for any convex polygon. Always. No cases.

The word “any” earns a look, and looking at it turns up a boundary.

What the construction does #

The molecule fills a polygon by shrinking it inward. Every edge moves toward the interior at the same rate, the corners trace straight lines as they go, and those traces are the creases.

Two facts make this work and they are both about convexity.

The inset stays a polygon. Move every edge of a convex polygon inward by the same amount and what is left is a smaller convex polygon with the same edges, until an edge shrinks to nothing. The corners move along straight lines because each is the intersection of two lines that are each translating at a constant rate.

The inset stays inside. A point that is at distance t from every edge of a convex polygon is inside it, by definition of convex — the polygon is the intersection of the half-planes its edges bound.

Neither holds for a polygon with a reflex corner.

It is worth appreciating how much those two facts buy, because they are the reason the molecule needs no cases at all. Together they say that the shrink of a convex polygon is another instance of the same problem — a smaller convex polygon, with the same construction available to it. A construction whose output is its own input is a construction that terminates by exhaustion rather than by case analysis, and that is the whole of the molecule’s universality.

Break either fact and the recursion breaks with it. A shrink that leaves the polygon is not an instance of anything; a shrink that splits it into two is two instances, which is fine in principle and requires the algorithm to know that it happened.

What goes wrong at a reflex corner #

A reflex corner is one that points inward, and at such a corner the two edges bounding it move away from each other as they shrink rather than toward each other.

The corner between them therefore travels outward — out of the polygon — and the inset stops being contained in the original almost immediately. Worse, the shrinking front reaches across the notch and meets itself: the region divides, and what was one polygon becomes two with their own separate shrinks.

That is the split event of the straight-skeleton literature, and handling it is a substantially harder algorithm. The fold-and-cut solver on this site refuses non-convex outlines for exactly the same reason, and the two refusals are the same refusal — both constructions are the same inward shrink, applied to different things for different purposes.

How far the shrink goes, and why that is the parameter #

Before leaving the convex case it is worth being precise about where it stops, because the stopping point is the one number a designer still has after the packing is fixed.

The shrink cannot continue indefinitely. Sooner or later an edge shrinks to zero length, or the inset polygon touches itself, and the construction has to stop. The generator finds that depth by bisection — it halves in on the largest inset that is still a convex polygon contained in the original — and the search is sixty steps deep, which is far more precision than the drawing needs and exactly the precision the assertion needs.

That bisection was not the first implementation, and the first one was wrong in an instructive way. Testing only whether the inset had positive area lets a corner escape: an edge that reaches zero length part-way through does not stop the remaining corners, which carry on along their traces and diverge, so an inset can have positive area with two of its corners a long way outside the original. The figures drew traces shooting off the canvas and the viewBox check caught it. Containment is the property the construction needs, so containment is what the bisection tests.

The parameter has a name #

The depth the bisection converges on is not an arbitrary output of a search. It is a named quantity, and saying which one turns the last free parameter from a number a program found into something a designer can compute by hand.

The inset at depth $t$ is the set of points at distance at least $t$ from every edge. For a convex polygon that set is non-empty exactly when $t$ is no more than the radius of the largest inscribed circle. So the depth the construction stops at is the polygon’s inradius, and the shrink’s final degenerate inset is the incentre.

That is checkable independently, which is the point of noticing it. A triangle’s inradius is its area over its semiperimeter, so a molecule filling a triangle of sides 3, 4 and 5 stops at $6/6 = 1$, and no bisection is needed to say so. For a general convex polygon the inradius is the answer to a small linear program — maximise $t$ subject to each edge’s half-plane inequality — which is exact where a bisection is merely converged.

It also gives a bound worth carrying: the inscribed circle’s area is at most the polygon’s, so $t \le 2A/P$ for area $A$ and perimeter $P$, with equality when every edge touches the circle. A long thin leftover region has a small inradius whatever its area, which is the arithmetic behind the observation further down that the pleats pile up where the region was narrowest.

Sixty steps is not a setting #

The bisection’s depth is worth a sentence for the same reason, because sixty looks like a number somebody chose and is not one.

Each step halves the interval, so sixty steps narrow a unit interval by a factor of $2^{60}$, around $10^{18}$. Double-precision arithmetic distinguishes numbers to about one part in $10^{16}$, which is fifty-three halvings.

So the search passes the resolution of its own arithmetic before it finishes, and the last several steps cannot move the answer at all. Sixty is not a precision target; it is a count comfortably past the point where the interval stops shrinking, chosen so that nobody has to think about where that point is.

The honest description of what it computes is therefore the inradius, to the last bit the arithmetic has — which is the right amount for an assertion to check against, and considerably more than a drawing needs.

The refusal is the right behaviour #

The generator here throws with a message saying the polygon cannot be shrunk at all, and that is better than the alternatives in a way worth spelling out.

An approximation would be worse. A construction that quietly produced something for a non-convex polygon would produce a crease pattern with no guarantee attached — and the guarantee is the entire reason the molecule is called universal. A pattern that passes every local test and folds wrongly is the failure mode this site is built to avoid, and a silently-approximated molecule is a machine for producing them.

A best-effort would also be worse, and more insidiously, because it would work often enough to be trusted. A shrink that ignored the containment failure would give correct answers for shallow reflex corners and wrong ones for deep ones, with no signal at the boundary.

So the construction’s scope is a thrown error rather than a caveat, and the figure at the top of this essay asserts the correspondence: convex succeeds, reflex fails, and if that ever stops being true the page does not build.

Where the difficulty went #

A construction that always works on its domain has not made the problem easy. It has moved the hard part into deciding what to hand it.

The regions between the discs of a packing are not convex in general. Some are, and those get a molecule directly. The rest have to be split into convex pieces first, and the split is a choice: a non-convex polygon can be cut into convex pieces in many ways, the pieces get different molecules, and the resulting crease patterns differ in how many creases they carry and how the layers stack.

That is the shape of the whole tree method and it is worth stating plainly. Each step is well-defined and the composition is a search. The packing is an optimisation with no known efficient solution. The decomposition into convex regions is a choice with no obvious criterion. Only the last step — the molecule itself — is a construction with a guarantee, and its guarantee is exactly what makes the earlier steps’ choices matter.

What a designer does instead #

In practice the difficulty is usually avoided rather than solved, and the avoidance is instructive.

Choose packings whose leftover regions are convex. A packing where the discs are arranged so that the gaps between them are triangles and quadrilaterals gives a design where every region takes a molecule directly. Designers develop an eye for this without necessarily framing it as convexity.

Add rivers. A river is the paper joining two flaps, and inserting one changes the shape of the regions around it. A river placed well can turn a non-convex gap into two convex ones, which is a design move that looks like it is about the model’s anatomy and is partly about the algorithm.

Use the grid. Box pleating sidesteps the whole question by restricting every crease to a grid at multiples of 45°, which makes the regions rectangles and triangles by construction. That the grid discipline also makes the molecules trivial is one of several reasons it dominates complex design.

All three are the same move: keep the input inside the construction’s domain, rather than extend the construction.

That is worth stating as a principle because it is the opposite of the instinct a programmer has. Faced with a function that rejects some inputs, the reflex is to widen the function. Here the widening is a research project — implementing split events correctly — and the alternative is to arrange the inputs, which is what the whole design tradition has done for thirty years without describing it that way.

It also explains something about how the method is taught. Books on the tree method spend their pages on packings and almost none on molecules, and the imbalance looks like an editorial choice about what is interesting. It is not: the molecule has nothing to decide, so there is nothing to teach beyond the construction, while the packing has everything to decide and no algorithm to decide it with.

Convexity is a strong requirement, quietly #

It is worth noticing how demanding the domain actually is, because “any convex polygon” sounds close to “any polygon” and is not.

Take a packing of discs in a square. The regions left between the discs are bounded by arcs and by the ridge and hinge creases the packing implies, and once those are straightened into an axial polygon the result is convex only when the discs around it are arranged conveniently. Four discs in a square leave a convex diamond in the middle; four discs in a line leave a long region that is not convex at all.

So a designer working with the tree method spends part of their attention on a question the method does not name: will the leftovers be convex? It is not in the algorithm’s statement, it is not what the packing is optimising, and it decides whether the last step runs at all.

That is the general hazard of a pipeline of well-specified steps. Each step has a clean contract, the contracts compose, and the difficulty settles into the joints between them where nothing is specified at all.

What no figure here can show #

The failures on this page are drawn as polygons with a note beside them, and that is the best available and not good. An error message is not a picture, and what actually happens inside the refused construction — the front reaching across the notch, the region dividing — is a motion that a static figure of a polygon does not convey.

Drawing it properly would mean implementing the split event, which is the thing being refused. That is a real circularity and it is why the figure reports the refusal rather than illustrating its cause: nothing here can draw what it declines to compute, and drawing a plausible sketch of it would be asserting a behaviour nobody here has checked.

The second absence is the crease pattern that a split-and-molecule approach would produce. Every figure here shows a single region. A design is dozens of them fitted together, and whether their patterns are mutually consistent — whether the layers of one region can stack with the layers of the next — is the global question this site does not answer.

The third is scale. Every polygon drawn here fills its canvas, and in a design the leftover regions are small — a few percent of the sheet each, packed between discs that took most of it. A molecule drawn at the size of the page looks like a substantial piece of construction; the same molecule at its real size is a dense knot of creases in a gap, and the density is what a folder meets rather than the geometry.

The idealisation, named #

The molecule’s guarantee is about the crease pattern and not about the folded object, and the gap between them is where a designer’s disappointment lives.

The construction produces a pattern whose creases are correct: the traces are straight, the inset distances are exact, and the pattern satisfies the vertex conditions. It does not produce a layer ordering, and it does not promise that the region’s layers stack compatibly with its neighbours’. Those are conditions on the assembled sheet, and no construction that works region by region can establish them.

And it assumes the paper has no thickness, which for a molecule is a specific rather than a general worry. A molecule fills a leftover region by pleating it away, and the pleats accumulate exactly where the region was smallest — so the thinnest part of the design carries the most layers. The crease radius that a real fold has is spent there first, which is why an ambitious base comes out short in precisely the places the geometry said were free.

Who found this, and when #

The universal molecule is Robert Lang’s, from the development of the tree method through the 1990s, and it is implemented in TreeMaker. The name is his and it is accurate about the right thing: it is universal over convex polygons, which is the domain the method arranges to give it.

The straight skeleton’s split events belong to the computational geometry literature — Oswin Aichholzer, Franz Aurenhammer, David Alberts and Bernd Gärtner set out the object in 1995 — and handling them correctly is a known and non-trivial piece of work. That the same construction shows up in fold-and-cut and in the molecule, with the same restriction and for the same reason, is one of the tidier coincidences in the subject.

It is not really a coincidence, of course, and saying why is the best summary of what a molecule is. Both constructions are answering the same question — how does a boundary get folded onto something smaller than itself — and the inward shrink is the answer because its corner traces are straight and its fronts stay equidistant. Fold-and-cut carries a boundary onto a line; the molecule carries a polygon’s boundary onto its own axis. Same machine, two jobs, one restriction.

Where this goes next #

A construction with a domain, refusing what falls outside it, is a piece of honesty about geometry. The same honesty about material is a different and blunter conversation: a sheet cannot be folded in half more than a handful of times, the bound is arithmetic rather than muscular, and it is the one limit in this subject that no idealisation removes.