From a packing to a crease pattern

A circle packing is a satisfying picture and an incomplete instruction. It says how long each flap is and where on the paper it starts, and it contains not one crease.

Getting from the packing to the pattern is the part of the tree method that is usually skipped, partly because it is less photogenic and partly because it is genuinely a construction — there is nothing to search for, and a step with no search in it attracts less attention than one with. It is worth the attention anyway, because the construction is what makes the packing mean anything.

What the packing has established #

A flap of length $L$ costs a disc of radius $L$, because every point of the sheet within $L$ of the flap’s tip is consumed in making it. Two flaps whose discs overlap are competing for the same paper.

So a packing is a proof of feasibility. It shows that the flaps a designer wants can coexist on a sheet of a given size, and finding one is the hard part of the whole method — a global optimisation with no useful convexity, which is why it is done by computer.

What a packing does not establish is any single fold. It fixes the tips of the flaps and their lengths; everything between the tips is unassigned paper, and that paper has to be got out of the way somehow.

Two families, and where each comes from #

Every crease in a uniaxial base is one of two kinds, and each is determined by the packing rather than chosen.

A hinge crease is where the paper changes which flap it belongs to. Two discs that touch are two flaps whose paper meets, and the boundary between them is the common tangent at the contact point: the line perpendicular to the line joining the centres, passing through the point where the circles meet. That point is at distance $r_1$ from the first centre and $r_2$ from the second, which is what “touching” means, and it is the only line that can separate the two flaps without taking paper from one of them.

A ridge crease is what happens in the region left over. Three or more discs that mutually touch leave a curved triangle of paper belonging to none of them, and that paper has to be folded down out of the way. It goes along the bisectors of the polygon whose corners are the disc centres — the axial polygon — because a bisector is the locus of points equidistant from two edges, and equidistant is what the paper has to be if it is going to fold into the same axis as everything else.

Reading a base off the finished pattern #

The two families are easy to tell apart once they are named, and telling them apart is how a crease pattern published without explanation can be read.

Hinge creases run in families of parallel lines, one family per pair of touching discs, and they are the creases that meet the edge of the paper. Ridge creases run between disc centres and their bisectors, they meet each other at points inside the sheet, and they never reach the boundary. A pattern in which the long straight creases all run to the paper’s edge is a pattern whose flaps are all on the boundary, which is what a base for a many-legged subject looks like; one whose creases are mostly interior belongs to a subject with flaps in the middle.

That reading is worth practising because it inverts the design process. The designer goes tree, packing, pattern. A reader with only the pattern goes backwards: find the ridge creases, recover the axial polygons, recover the disc centres, and the tree falls out. The pattern really does contain the whole design, which is the claim this site’s second thread is named for.

Why a hinge is perpendicular #

The perpendicularity is the one part of the construction that deserves a derivation rather than a statement, because it is the part that makes the base uniaxial.

A uniaxial base has every flap lying on a single line — the axis. Paper on one side of a hinge folds into one flap, paper on the other side into its neighbour, and both flaps must end up on the same axis. The fold that carries the paper from one flap’s direction into the other’s is a reflection, and the reflection has to take the first disc’s centre onto the axis at the right distance and the second disc’s centre likewise.

The only line that does both is the perpendicular bisector of the segment between the two contact-adjusted centres, and when the discs are tangent that is precisely the common tangent at the contact point. So the hinge is not a choice with a nice property; it is the unique line that can be there.

The figure asserts this rather than displaying it. Before drawing, it checks that each contact point is at exactly its own disc’s radius from each centre, and that the crease it draws has zero dot product with the line of centres. Both are the sort of thing that a drawing gets subtly wrong — a disc a fraction too large, a crease drawn to look right — and neither would be visible.

What the axial polygon adds #

The regions between the discs are where the method stops being local, and they are the reason two designers with the same packing can produce different patterns.

Each such region is a polygon whose corners are disc centres and whose edges are the lines between touching discs. The paper inside it is not part of any flap. It has to be folded so that it disappears into the axis, and the folding is a molecule: a small crease pattern filling the polygon, whose boundary matches the hinges already fixed around it.

For a triangle the molecule is easy and unique — three bisectors meeting at the incentre, which is the rabbit-ear. For a quadrilateral there are several. For a general polygon the question of whether a molecule exists at all is not obvious, and the construction that always works is the last piece of the method and the one with a free parameter still in it.

What a river does to the construction #

The tree method’s flaps meet each other at the tree’s internal nodes, and those nodes have to be somewhere on the paper too. The device for that is a river: a band of a stated width running between two parts of the tree, which the packing must accommodate along with the discs.

The construction above survives this unchanged in form and changes in detail. A hinge is still the crease where the paper changes allegiance, and it is still the common tangent — but the tangent is now to two offset curves rather than to two circles, because a river’s boundary is a pair of parallel curves at the river’s half-width from the tree edge it represents.

The practical consequence is that rivers make the packing harder and the pattern no harder. That is the usual shape of things in this method: every refinement lands on the optimisation and none of it lands on the construction, which is why the construction is the part that can be automated with confidence and the packing is the part that needs a good optimiser and a long afternoon.

Why the triangle is the only easy molecule #

The remark that a triangle’s molecule is unique and a quadrilateral’s is not looks like a fact about how much work has been done on each. It is not: the two cases differ by a theorem, and naming it says where the free parameter comes from.

A molecule folds its polygon into the axis, which means every point of it must end up at its own distance from the boundary — so the creases run along the angle bisectors, each being the locus of points equidistant from two edges.

For a triangle the three bisectors are concurrent. They meet at the incentre, there is one such point, and the molecule is therefore forced: three creases to one point, which is the rabbit-ear. The uniqueness is the concurrency, and nothing else.

From four sides up, bisectors are not concurrent in general. Four bisectors of a general quadrilateral meet in pairs at up to six distinct points, so there is no single place for the paper to gather and the construction has to choose — which is exactly the free parameter the general molecule still carries.

And the ridges handle more paper than the flaps waste #

The leftover regions are described as what is between the discs, which understates them. Their area is $1 - e$ for a packing of efficiency $e$, and that is not a remainder — it is the whole of the model’s body.

At the best arrangement small counts reach, $e = \pi/4$, so 21.5% of the sheet is ridge material. At the 66% a square typically manages it is 34%: a third of the paper, folded by creases nobody drew a disc for.

That gives the method a trade it does not usually state. Packing better lengthens the flaps and shrinks the body — going from 66% to 78.5% cuts the body’s paper by more than a third — so a design wanting a substantial thorax is a design that should not be packed to the limit. Efficiency is not free; it is paid for out of the part of the subject the tree never described.

Which theorem was checked, and how #

There is no theorem here, and that is the point of the rung: after the packing, the pattern is a construction and the only things to check are that the construction was carried out.

The figure checks three. No two discs overlap — measured as a distance against a sum of radii, and the generator refuses a configuration where any pair overlaps by more than a billionth. Every contact point lies on both circles. Every hinge is perpendicular to its line of centres. Those are the three ways a drawing of this could be wrong while looking entirely convincing.

What is not checked is that the resulting pattern folds flat, because the figure draws hinges and axial lines rather than a complete pattern with an assignment. That is stated on the figure and it matters: a complete uniaxial base needs its molecules filled in and its assignment found, and the assignment is not free.

What the picture cannot show #

The figure shows a five-disc packing on a square — four corners and one in the middle — which is the simplest packing with an interesting region in it. Real packings from real subjects have twenty or fifty discs of differing radii, arranged by an optimiser, and their axial polygons are irregular.

More significantly, the picture is flat and the object is not. The hinges and ridges drawn here are creases in the unfolded sheet; what they do is carry the paper into a shape where every flap lies along one line, and that shape is three-dimensional and is not drawn. The correspondence between a line on the flat sheet and a fold in the finished base is exactly the thing a reader has to hold in mind, and no single picture supplies it.

Where the construction stops being automatic #

Three places, and each one is a decision a person makes.

The first is which discs are taken to be touching. A packing produced by an optimiser has contacts that are exact and near-contacts that are a thousandth of a sheet-width apart, and treating a near-contact as a contact adds a hinge that need not be there while refusing it leaves a region with an extra corner. The figure here uses an exact test with a tolerance of a billionth, which is honest for a packing computed in closed form and useless for one that came out of an optimiser. In practice the tolerance is a judgement.

The second is the molecule. A quadrilateral axial polygon can be filled several ways, and the choices differ in how many layers pile up and where — which matters enormously for a folder and not at all for the mathematics.

The third is the assignment. Nothing in the packing or the construction says which creases are mountains and which valleys. That has to be found afterwards, subject to the conditions at every vertex, and for a base of any size the number of candidates is large enough that a search is required.

None of the three is a gap in the method. They are the places where the method hands back control, and a designer who knows where they are can work with the construction instead of against it.

The idealisation underneath #

The method assumes the flaps are lines — that a flap of length $L$ is a segment with no width, so that the paper it needs is a disc.

Real flaps have width, because real paper has thickness and a flap folded to zero width will not stay closed. The tree method’s answer is to inflate the tree’s edges into rivers of a stated width, at which point the discs become annular regions and the packing problem becomes harder. The river is what a flap’s width costs, and the construction above runs unchanged with rivers in it — the hinge is still the common tangent, and the tangent is now to two offset curves rather than to two circles.

The second idealisation is scale-free: nothing in the packing or the construction refers to the size of the paper. That is true of the mathematics and false of the practice, since a crease has a radius and a base with two hundred creases loses a measurable amount of paper to them.

Why the construction has no search in it #

It is worth dwelling on how unusual this step is, given the company it keeps.

The packing before it is a global optimisation with many local minima. The assignment after it is a combinatorial search over an exponentially large space. Between them sits a step in which nothing is searched for at all: every crease is the unique line satisfying a condition that has one solution.

That is the shape of a well-posed sub-problem, and it is the reason the tree method is a method rather than a heuristic. If the crease construction had choices in it, a designer would have to trade the packing against the pattern — a better packing might yield a worse set of creases — and the two would have to be optimised together. They do not, so the packing can be optimised alone and the pattern read off afterwards.

The one exception is the molecule, and Lang’s universal molecule exists precisely to remove it: a construction that always works, so that the polygon-filling step joins the rest of the determinate part instead of adding another search. What it leaves behind is a single number rather than a choice, and that number is the subject of the next rung.

The surprising connection #

The bisector construction that fills an axial polygon is the straight skeleton, which is the same object that appears in the fold-and-cut theorem — where it is used to fold a shape’s outline onto a single line so one cut releases it.

That is not a coincidence and it is not a metaphor. Both constructions are answering the same question: given a polygon, fold it so that its entire boundary lands on one line. In the fold-and-cut case the line is where the scissors go. In the design case the line is the axis of the base. The construction does not know or care which, and a designer who has understood one has understood the other.

Who found it, and when #

The tree method is Robert Lang’s, developed through the 1990s and implemented in TreeMaker; Toshiyuki Meguro and Jun Maekawa arrived at circle packing independently in Japan in the same period, and the tsujiura tradition of packing-based design predates the formal statement.

The specific decomposition into hinge and ridge creases, and the language of axial polygons and molecules, is Lang’s and is set out in Origami Design Secrets. The proof that the universal molecule always exists for a polygon satisfying the path condition is his too, and it is the result that turns a heuristic into a method.

The ladder from here #

This rung takes a packing and produces every crease except those inside the axial polygons. The next fills them, which is where the last free parameter of the whole design lives — the one number that the packing does not fix.

Above that the ladder leaves construction for economics: how much paper the method wastes is a question about the packing, and the answer explains why competition-level designs use a square rather than a rectangle, and why they use a large one.