Origami & Folding
what one sheet can do
Series

Search order — the series

9 essays on one idea, from the one that introduces it to the one that assumes the rest.
  1. heavier means the crease lies on more independent circuits157 panels, 282 arcs, circuit rank 126; circuits run from 4 to 26 arcs

    Which choice the cost lives in

    A backtracking search takes two decisions at every step — which thing to decide, and what to decide about it. The literature is almost entirely about the first. On these crease patterns the whole of the cost was in the second, and the structural improvement everybody reaches for first makes matters worse on fifty-two patterns out of eighty-seven.

    part 1 · complexity
  2. each cell is one patch, searched to a verdictgreen: a lettering exists · magenta: none exists, by exhaustion0.150.250.350.50.70.91.11.3turn angle, in radianssquare2626262626262626elongated1515323231313232hexagonal1515394545464545triangular1515393939373737the number in a cell is the nodes the search visited; 6 of 32 patches have no lettering at all

    The order that proves nothing exists

    Twelve crease patterns with no consistent lettering at all. Proving it takes fifteen steps under one rule and half a million under another — and on three of the twelve the two rules swap places, so neither is the good one. The cost of a negative is two to the power of how many free choices sit above the contradiction.

    part 2 · complexity
  3. the same drawing, cut out of the plane and glued upnodes, log scale, against periods across the sheet10100100010⁴10⁵1×12×23×34×4glued upcut outan open mark is a search that ran out of budget rather than a cost

    What the rim was doing

    One rectangle of a twist tessellation, cut out of the plane in the ordinary way, gives up a consistent lettering in forty-eight steps. Join its opposite edges so that no crease is divided and the same drawing, at the same vertices, under the same conditions, takes fifty-six thousand seven hundred and seventy-two. The edge of the paper was never the difficulty. It was the slack.

    part 3 · complexity
  4. proving the glued square cell has no lettering1×1, 4 panels3proved there is none · the other test found one in 32×2, 16 panels35proved there is none · the other test found one in 93×3, 36 panels3,455proved there is none · the other test found one in 6254×4, 64 panels200,000still running at the budgeta bar at the budget is a search still running, not a proof

    Pruning on proofs alone

    A search that discards a branch it cannot prove wrong is not a search. Deciding whether a periodic pattern's layer relations really contradict themselves is far dearer than the disc's one-pass test, so the cheap test is asked first — it is sufficient, so it settles almost everything — and the expensive one runs only on what the cheap one rejects. Five of nine steps on a small cell, fifty thousand of fifty-seven on a large one.

    part 4 · complexity
  5. what each sheet costs, per panel — a square twistcut out ×10.5565 nodes on 9 panels · 12 lettersglued across ×10.6674 nodes on 6 panels · 10 lettersglued along ×10.6674 nodes on 6 panels · 10 lettersglued both ways ×10.7503 nodes on 4 panels · 8 letterscut out ×20.52013 nodes on 25 panels · 40 lettersglued across ×20.55011 nodes on 20 panels · 36 lettersglued along ×20.55011 nodes on 20 panels · 36 lettersglued both ways ×20.5639 nodes on 16 panels · 32 letterscut out ×30.61230 nodes on 49 panels · 84 lettersglued across ×32.02485 nodes on 42 panels · 78 lettersglued along ×30.57124 nodes on 42 panels · 78 lettersglued both ways ×317.361625 nodes on 36 panels · 72 lettersthe letters go down as the rim goes and the cost per panel goes up

    Half the slack

    Gluing one pair of a cell's edges removes half the free letters and costs almost nothing. Gluing the second pair removes the other half and costs three orders of magnitude. The letters go linearly and the search does not, and the reason is that the last free letter is worth more than all the others.

    part 5 · complexity
  6. the Yoshimura, 2×2 cellsone drawing, four sheetscutoutgluedacrossgluedalonggluedboth waysvertices8888free letters36283224panels29202416V − E + F1000the vertex row is the control: identifying edges can neither make nor destroy a vertexand Euler's number is the cheapest check that the gluing did what it says

    Which pair is glued

    A cell's two cylinders have the same Euler number, the same amount of rim and the same name. On a symmetric drawing they have identical counts of letters, panels and vertices — and searching them costs twenty-four nodes one way and eighty-five the other. Half the rim is a description of the topology and not of the object.

    part 6 · complexity
  7. the cost of one lettering, by size and by how the cell is gluednodes of search, under one fixed branch orderperiodsfree lettersa discone cylinderthe othera torustorus over discthe square grid1×11254430.62×240131212131.03×384262428532.04×4144456244116926.05×52207066209292741.8the honeycomb1×1341291080.72×2116403439952.43×324676285386418655.1the triangular grid1×13412101080.72×2116373134166845.13×324691570524!12000131.9the rhombille tiling1×160226218160.72×2216!12000!120001009!120001.0a plus sign is a search that ran out of budget rather than out of possibilities; the free letters are the cut sheet's

    Each drawing has its own threshold

    Gluing a cell's edges was measured once, at one size, and found to cost three orders of magnitude — which cannot tell a threshold from a slope, nor say whether a cut sheet has one further out. Swept from one period to five on four tilings, every sheet starts at about a third of a node per free letter and every drawing leaves that behaviour at a size of its own: four periods on the square grid, three on the honeycomb, two on the triangular grid and two on the rhombille, where even the cut sheet crosses.

    part 7 · complexity
  8. what ten branch orders cost on the same four sheetsnodes of search; the sheets are the same drawings as the sweep abovethe square grid, 4×4, glued69 to 24636, 1 gave upthe square grid, 4×4, cut42 to 55the square grid, 3×3, glued20 to 731the square grid, 3×3, cut25 to 32each bar runs from the cheapest of 8 branch orders to the dearest, on a logarithmic scale; a dot is the middle one

    The route, not the sheet

    Every cost measured for a glued sheet has been one number from one branch order, and a backtracking search's cost belongs to the pair. Asked under eight orders instead of one, a cut cell's cost barely moves — 42 to 55 nodes — while the torus over the same drawing runs from 69 to 24,636, with one order giving up entirely. The glued sheet's best order costs less than twice the cut sheet's, so most of what a single order charged to the gluing belongs to the route through it.

    part 8 · complexity
  9. nodes per free letter, cheapest route against the middle onecheapest of eightmiddle of eight× where no route of that kind finished · periods along the bottom0.3110100×2345the square grid, glued×123the triangular grid, glued××1234the honeycomb, glued0.3110100×123the elongated triangular tiling, glued××12the rhombille tiling, glued×123the rhombille tiling, cut

    The cheapest route crosses later

    A search for a consistent lettering has a threshold: below it the letters propagate and the cost is a third of a node per crease, above it the search backtracks and the cost explodes. The threshold was measured with one branch order. Measured with eight, the cheapest route never starts searching before the typical one, and on most sheets it starts a period or two later — so part of every threshold on the record belongs to the route. And the one cut sheet past its threshold, the rhombille's, spreads across nearly three orders of magnitude of cost, which moves the spread off the gluing and onto the threshold.

    part 9 · complexity

All series