Geometric Folding Algorithms:
Linkages, Origami, and Polyhedra

Erik D. Demaine and Joseph O'Rourke

Table of Contents

• Figure 0.1: There is a linkage that traces a thin version of this collection of curves. page 12

• Figure 0.2: A “mule deer” folded by Robert Lang (opus 421): http://www.langorigami.com/art/gallery/gallery.php4?name=mule_deer. The crease pattern was designed using TreeMaker. page 13

• Figure 0.3: A net for the snub cube, drawn by Dürer. page 14

• Figure 0.4: (a) A 3 × 3 map that can be folded (but not easily!) [cf. Figure 14.1]; (b) a 2 × 5 map that cannot be folded [Jus94]. page 16
• Figure 0.5: A polygon that folds to a convex polyhedron of 16 triangular faces. page 16

• Linkage Definitions page 21
• Overview page 21
• Figure 1.1: A linkage. The circles represent joints at which turning is possible; the two leftmost joints are pinned to the plane. The shaded “lamp” structure is rigid (because of the interior diagonals). page 22

• Table 1.1: Classification parameters for 1D linkage problems. page 24

• Figure 1.2: A six-axis robot arm. [By permission, Forward Thompson Ltd.] page 25

• Figure 1.3: A pantograph. Joint x is pinned. The movement of joint y is duplicated and doubled by point z. page 26
• Figure 1.4: Thomas Jefferson's pantograph (1804). Thomas Jefferson Polygraph (i.e., pantograph), 1804. Special Collections, University of Virginia Library. By permission. page 26

• Figure 1.5: (a) The part is about to be creased by the punch moving vertically into the well of the die; (b) after creasing. page 27

• Figure 1.6: Two views of the backbone of a protein of 236 amino acids, the so-called “green fluorescent protein” (GFP), code 1EMB in the Protein Data Base. Images generated by Protein Explorer, http://proteinexplorer.org. page 29

• Figure 2.1: (a) Arm and obstacles; (b) (θ₁, θ₂) configuration space. s and t mark initial and final positions. Based on Figure 2 in [HA92]. page 32
• Box 2.1: Cylindrical Algebraic Decomposition page 33
• Box 2.2: Roadmap Algorithm page 33

• Figure 2.2: Wooden “Hedgehog in a Cage” puzzle. http://www.cleverwood.com/. page 36

• History page 37
• Table 2.1: Lower bounds. “Simple” means non-self-intersecting. page 38

• Figure 2.3: The movable object P consists of a series of identical tetrahedra linked by segments. It is poised to enter a “tunnel” Q (at the darkly shaded portals). Each cylindrical fan of triangular tunnels represent one state of the machine, with one triangle per possible tape symbol. Connecting several such tunnels together forces P to change states in a determined way. (After Figure 10 of [Rei79].) page 39
• Figure 2.4: The moving chain is C. The backward and forward position of the “switch” whose tip is x encodes the bit 0 and 1. The gadget shown checks the bit in the sense that if C starts below the obstacle A with the switch backwards as in (a), it cannot move to above A. If, however, the switch is initially forward as in (b), x can enter the circular well and open enough to shorten the chain, permitting passage to above A. (After Figure 5 of [JP85].) page 40
• Ruler Folding page 40
• Figure 2.5: Ruler folding reduction. Here x₁+x₃+x₄=x₂+x₅+x₆. page 41
• Figure 2.6: (a) Initial configuration. The dashed segment starting from v₀ represents a large collection of unit links. The slashes indicate interruptions. Note the tunnel is only 2 + ε units high. (b) Intermediate configuration, when R₁₀₀ is folded and about to pass through the gap. page 42
• Path Planning page 43
• Universality Theorem page 43

• Figure 3.1: A Watt linkage. Joints x and y are pinned; joints a and b are free. The locus of point c is the figure-8 curve. [Construction from Cinderella.] page 46

• Figure 3.2: Peaucellier linkage. The dark lines show it in one position, the light lines in another. page 47

• Figure 3.3: Linkage parallelogram. page 49
• Multiplicator page 49
• Figure 3.4: A contraparallelogram. |xa| = |yb| and |xy| = |ab|. (Note: there is no joint at the point at which the two rods xy and ab cross.) page 50
• Figure 3.5: Kempe's “Multiplicator”: two nested, similar contraparallelograms. page 50
• Figure 3.6: Kempe's angle trisector [Kem77, p. 42]. page 51
• Additor page 51
• Figure 3.7: (a) A reflects to A′ about C, as does B to B′; (b) The construction with superimposed reversors. page 52
• Translator page 53
• Figure 3.8: (a) Kempe's Translator; (b) Alignment of C with B; (c) Second parallelogram flips to a contraparallelogram. [See also Fig. 2.3.2 of [HJW84].] page 53
• Overall Design page 54

• Figure 3.9: A schematic of the overall structure of Kempe's construction. Each term of Equation (3.2) is simulated by a link whose projection on the horizontal axis is that term. The point p′ is constrained to follow a particular vertical line by a Peaucellier linkage. The joints labeled O are the same joint. page 55
• Figure 3.10: Simulating a joint in the interior of a link. page 56

• Figure 3.11: (a,b,c) Three circular motions of a rhombus; (d) rhombus rigidified. page 57
• Figure 3.12: (a) Braced contraparallelogram; (b) Flipping to the corresponding parallelogram is not possible. page 57
• Box 3.1: Braced Contraparallelogram page 58

• Open Problem 3.1: Continuous Kempe Motion page 59
• Open Problem 3.2: Noncrossing Linkage to Sign Your Name page 59

• Figure 3.13: Hart's inversor. |ab| = |cd| and |bc| = |da|, so that abcd is a contraparallelogram. page 60
• Figure 3.14: Hart's mechanism to convert circular motion of y to linear motion of y′. Joint x is pinned and the center of inversion. L is perpendicular to the line containing xz. page 60
• Box 3.2: Geometry of Hart Inversor page 61

• Figure 4.1: (a–c): rigid; (d): flexible. In (b), the bars are not joined at the hexagon center. page 64

• Figure 4.2: Dependence of rigidity on configuration. (a) Rigid embedding: the shaded triangles pull the chain containing x and y taut. (b) Flexible embedding: the link yx can move left or right. (See also Figure 4.8 below.) page 65

• Figure 4.3: Schematic definition of generic rigidity and generic flexibility. page 66
• Figure 4.4: (a) generically rigid; (b) rarely flexible; (c) generically flexible; (d) rarely rigid. page 66
• Open Problem 4.1: Faster Generic Rigidity in 2D page 67

• Figure 4.5: The “double banana” example which satisfies Laman's combinatorial condition yet is generically flexible: the bananas can pivot around the dotted line. page 68
• Open Problem 4.2: Generic Rigidity in 3D page 68

• Figure 4.6: A Henneberg sequence: (a) A single edge; (b) Construction 1 adds a new vertex; (c) Construction 2 deletes an edge and adds a new vertex. page 69

• Open Problem 4.3: Realizing Generically Globally Rigid Graphs page 70

• Box 4.1: Rigidity Matrix page 73

• Figure 4.8: The movement of x illustrated projects so that the incident bars do not lengthen. So the linkage is infinitesimally flexible. But the linkage is in fact rigid, because the three collinear bars are stretched taut by the rigid shaded quadrilateral. [Based on Figure 3.8 of [Gra01].] page 75
• Figure 4.9: Rigidity and flexibility hierarchies of all configurations (of all linkages). The hierarchies are hypothetical for kth order, k ≥ 3. [Based loosely on Figure 2 of [CW96].] page 75

• Figure 4.10: Tensegrities. (a–c) are flexible; (d) is rigid, even globally. (a–b) follow from Theorems 6.6.1 and 6.7.2, respectively; (c–d) are based on [CW96, Fig.3], [Con93, Fig. 4.2]. page 76

• Figure 4.11: Examples of equilibrium stresses in tensegrities. Here we suppose that all edges are bars, but edges with negative stresses could be struts and edges with positive stresses could be cables. page 79

• Figure 4.12: A triangulated planar graph, and a polyhedral lifting. page 81
• Figure 4.13: Characterizing edges in a polyhedral lifting as valleys or mountains. The thick edges denote the intersection with a vertical plane. [Fig. 8 of [CDR02b].] page 82

• Figure 5.1: An arm/pinned open chain. The angle α_i is the turn angle between adjacent links. page 84

• Figure 5.2: Annulus sum. page 85
• Figure 5.3: The vector sum e₁+e₂+e₃ is independent of the order of the terms. page 86
• Figure 5.4: Inner radius r_i=ℓ_M−s. page 86

• Figure 5.5: (a) (ℓ_M=6) > (s = 5); (b) (ℓ_M=6) < (s = 15); (ℓ_M′=8) ≤ (s′ = 9). page 87

• Figure 5.6: Inversion of a closed polygonal chain. The links are marked with their lengths. The sequence is inverted from (6, 3, 5, 4, 1) to (1, 4, 5, 3, 6). page 89
• Figure 5.7: A noninvertible polygon, with link lengths (6, 1, 5, 4, 1). page 89
• Figure 5.8: Under the permutation π = (1, 3, 2, 5, 4), (a) is altered to (b). page 90
• Figure 5.9: ℓ₁−ℓ₂ and the remainder of the chain are insufficient to span ℓ₃. (The link lengths here are those used in Figure 5.7: 5 + 4 > 6 + 1 + 1.) page 91
• Figure 5.10: A line-tracking motion. The initial position of the chain is shown with solid lines, with v₂ tracking line L to positions v′₂ and v”₂. This is not a simple line-tracking motion because the angle at v₃ changes nonmonotonically, as indicated by the angle measurements. page 92

• Figure 5.11: The long links must remain near a diameter. The consecutive pairs of short links each can be placed left or right of that diameter. This yields 2^n/3 disconnected configurations. page 93
• Figure 5.12: (a) The five links have orientations LLRRL; (b) orientations RLLLR. Thus all but L₂ are reoriented. page 94
• Figure 5.13: Normal form for the chain shown in Figure 5.12(a). page 94

• Figure 5.14: Link L₁=(v₀, v₁) is “stuck” because it cannot reorient to “aim” toward corner c. page 95

• Figure 5.15: There are chains with link lengths in the shaded regions (0.483, 0.500] and (0.866, 1.000] that cannot fold. page 96

• Figure 5.16: “Stuck” chains: (a) x₁ > 0.483; (b) x₂=0.5; (c) x₃ > 0.866. page 97
• Figure 5.17: (a) Left and Right in neighborhood of a vertex; (b) C = (v₀, …, v₈) does not self-cross, for it stays on the same side of v₀v₁ both in a neighborhood of v₃, and in neighborhoods of v₆ and v₇. But if v₈ is replaced by v′₈, then C′ = (v₀, …, v′₈) does self-cross. page 97
• Box 5.1: Self-Crossing page 98

• Figure 5.18: The sign sequence (−, +, −, +, −) alternates four times. page 99
• Figure 5.19: The inscribed quadrangle (v_i, v_j, v_k, v_l). page 100
• Figure 5.20: Flexing a quadrangle [After Figure 2 in [ADE⁺01]]. page 100

• Figure 5.21: A planar arc partially lifted into a vertical line. page 102

• Figure 5.22: Flipping several pockets simultaneously can lead to crossings [dSN39]. page 102
• Figure 5.23: (a) Flipping a polygon until it is convex. Pockets are shaded. (b) The first flip shown in 3D. page 103
• Figure 5.24: Quadrangles can require arbitrarily many flips to convexify. page 104
• Open Problem 5.1: Pocket Flip Bounds page 104
• Open Problem 5.2: Shortest Pocket-Flip Sequence page 104
• Figure 5.25: The distance from x to v_i is increased by a flip. page 105
• Figure 5.26: Red lines indicate the subset relation. Here P⁰ ⊆ C⁰ ⊈ P¹. page 106
• Box 5.2: Proof Pitfalls page 107

• Figure 5.27: (a) Original polygon P₀, with lengths 3 + 6 = 4 + 5; (b) deflation step; (c) P₁; (d) deflation step; (e) P₂; (f) deflation step. page 108
• Figure 5.28: An attempted deflation produces a self-crossing polygon. page 109

• Figure 5.29: A polygon P such that every pop produces a self-crossing. Four of the 8 pops are illustrated. page 110
• Open Problem 5.3: Pops page 111

• Convex Arch Algorithm page 111
• Figure 5.30: v_i + 1 rotates up the circle C until it hits Π_ε. page 111
• Figure 5.31: (a) The arch in Π_z after the i-th step; (b) After lifting v_i + 1, the arch is rotated down to the plane Π_ε; (c) After reconvexification in Π_ε “absorbs” v′_i, the arch can be safely rotated about its new base edge to a vertical plane again . page 112
• Quadrilateral Arch Algorithm page 112
• Figure 5.32: (a) The arch at a generic step; (b) v_i and v_j have been lifted slightly, producing a twisted trapezoid v_iv_i − 1v_j + 1v_j. page 113
• Figure 5.33: The centers of the spheres S_a and S_b are a′ and b′ respectively. The initial and final positions of a′a and b′b are shown shaded. page 113

• Figure 5.34: A 3D polygon that has a simple projection in the plane below. page 114
• Figure 5.35: (a) Step 0: e₀ is rotated within Π₁ and then into Π₂. (b) Step i: The chain translates within Π_i. page 115

• Figure 6.1: Three common linkages (open, and closed chains, and trees) and their associated canonical configurations (straight, convex, and flat). page 118
• Table 6.1: Summary of Locked and Unlocked Results. page 118

• Figure 6.2: The “knitting needles” locked chain. The standard knot theory convention is followed to denote “over” and “under” relations. page 120
• Figure 6.3: B is centered on the midpoint m along (v₁, v₂, v₃, v₄). A reconfiguration of v₁ to v′₁ and v₀ to v′₀ illustrates that v₁ remains interior and v₀ remains exterior to B. page 121

• Figure 6.4: K² (K doubled): a locked but unknotted chain.. page 122
• Figure 6.5: (a) Cantarella and Johnson locked hexagon; (b) Toussaint locked hexagon; (c) Lengths from [CJ98] for (a); (d) Lengths from [Tou01] for (b). The latter two are perspective projections from 3D. page 123

• Open Problem 6.1: Equilateral Fat 5-Chain page 123
• Figure 6.6: A “fat” chain of five links. Is it locked? [Figure created in collaboration with Sorina Chircu.] page 124

• Open Chains in 4D page 125
• Closed Chains in 4D page 125
• Figure 6.7: Snapshots of the algorithm straightening a chain of n = 100 vertices, initially (0), and after 25, 50, 75, and all 99 joints have been straightened (left to right). (a) Scale approx. 50:1; the entire chain is visible in each frame. (b) Scale approx. 1:1; the straightened tail is “off-screen.” (The apparent link length changes are an artifact of the orthographic projection of the 4D chain down to 2D.) [Fig. 7 in [CO01], by permission, Elsevier.] page 126

• Figure 6.9: Locked planar polygonal trees. Points in shaded circles are closer than they appear. page 128

• Figure 6.10: Two views of convexifying a polygon that comes from doubling each edge in the locked tree from Figure 6.9(b). The top snapshots are all scaled the same, and the bottom snapshots are scaled differently to improve visibility. [Fig. 1 in [CDR03], by permission, Springer.] page 130
• Expansiveness page 130
• Multiple chains page 130
• Open Problem 6.2: Unlocking Nested Chains page 130
• Figure 6.11: The nested open chain cannot be straightened inside the containing closed chain because of the lack of space. [Fig. 2 in [CDR03], by permission, Springer.] page 131
• Theorem page 131
• Figure 6.12: Four frames in the unlocking of four polygonal chains. The initial disjoint collection is shown in the leftmost frame. page 132
• Figure 6.13: Three frames toward the end of the unlocking motion, continuing Figure 6.12 at a different scale. [Figs. 1 and 2 in [O'R00a].] page 132

• Initial simplifications page 133
• Duality page 133
• Planarization page 133
• Figure 6.14: The first three modifications to the collection of chains. (a) Original collection. (b) With straight vertices removed. (c) With convex cycles rigidified. (d) With components nested within convex cycles removed. page 134
• Figure 6.15: Planarizing the tensegrity of the chain's bars and all other struts. [Based on Fig. 6 of [CDR03].] page 134
• Maxwell-Cremona lift page 135
• Intuition page 136
• Maximum z page 136
• Figure 6.16: Slicing below a vertex local peak. page 137

• Convex optimization page 140
• Ordinary differential equation page 140
• Forward Euler algorithm page 140
• Global error bound page 141
• Putting the pieces together page 141
• Summary page 141

• Figure 6.17: Convexification by a sequence of single-degree-of-freedom expansive mechanisms. [Figure courtesy of Ileana Streinu and Elif Tosun.] page 142
• Pseudotriangulations page 142
• Figure 6.18: Two pointed pseudotriangulations of the same set of 10 points. page 143
• Unlocking chains page 143
• Mechanisms page 144
• Flipping page 145
• Figure 6.19: This flip in pseudotriangulation of single-degree-of-freedom mechanism is triggered by the collinearity in (b). The shaded triangles remain rigid throughout the motion. page 146
• Algorithms page 146
• Extensions page 146

• Figure 6.20: Convexifying a 29-link closed chain via gradient descent of energy. [From [CDIO04].] page 147
• Figure 6.21: Convexifying a 380-link closed chain via gradient descent of energy. [From [CDIO04].] page 147
• Open Problem 6.3: Polynomial Number of Moves page 148

• Figure 6.22: Convexifying a common polygon via all three convexification methods. [Fig. 9.3.3 [CD04], by permission, CRC.] page 149
• Open Problem 6.4: Characterize Locked Linkages page 150
• Proving linkages locked page 150

• Figure 6.23: Self-touching configurations resulting from Figure 6.9 by contracting the dotted circles down to points. Only the geometry is illustrated; additional combinatorial information is specified by the insides of the dotted circles in Figure 6.9, and by the number of links along each edge. page 151

• Step 1: Model as self-touching configuration page 153
• Figure 6.24: (a) Locked tree. (b) Self-touching version. (c) One petal and adjacent pieces. Short light edges denote zero-length sliding struts. Blow-Ups show the signs of stresses on edges to achieve equilibrium; thick edges carry stress; and dotted edges show negations of + edges. page 154
• Step 2: Prove corresponding linkage infinitesimally rigid page 155
• Step 3: Find equilibrium stress page 155
• Figure 6.25: Possible sign patterns for an equilibrium stress at a degree-3 vertex (when no two of the edges are collinear). [Fig. 10 in [CDR02a], by permission, American Mathematical Society.] page 156
• Finale of the argument page 156

• Open Problem 6.5: Self-touching Chains page 156

• Figure 6.26: A 3D polygon P that has a simple projection P′ in the plane below. page 157
• Figure 6.27: Pulling vertex b rightwards straightens the planar, monotone chain to a segment, while maintaining the heights of both endpoints a and b. page 158
• Figure 6.28: Blue edges are “springs.” (a) ab is fixed and c moves vertically; (b) ac rotates about a; (c) dc′ has become taut; (d) c′d rotates about c′. page 160

• Figure 7.1: An n = 17 link chain that requires cutting at least ⌊(n − 1)/4⌋ = 4 vertices to separate. [Fig. 1 in [DLOS03], by permission, Elsevier.] page 161
• Open Problem 7.1: Unlocking Chains by Cutting page 162
• Table 7.1: Interlocking pairs of chains. (+) = can lock, and (−) = cannot lock. kf = open, flexible k-chain; △ = closed (rigid) 3-chain; □ = closed, flexible 4-chain; pentagon = closed, flexible 5-chain. page 163

• Figure 7.2: Three 2-chains (solid) scaled (dashed) by s = 2. The clipping for one chain (blue, lying in a vertical plane) is detailed. page 164
• Open Problem 7.2: Interlocking a Flexible 2-chain page 164

• Figure 7.3: Nonuniform scaling keeps the middle links parallel to the xy-plane. (Scaled versions of the end links are not shown.) page 165
• Figure 7.4: A quadrilateral and a 3-chain can lock. [Fig. 6 in [DLOS03], by permission, Elsevier.] page 166

• Figure 7.5: A triangle and a 4-chain can lock. [Fig. 2 in [DLOS03], by permission, Elsevier.] page 167
• Figure 7.6: The first few two-component links. Images produced by knotplot: http://www.knotplot.com/. page 167
• Box 7.1: Topological Links page 167
• Figure 7.7: When v₀ touches B, point v₁ must be exterior to B′ by at least R, and therefore v₂ and v₃ are also exterior to B′. [Fig. 3 in [DLOS03], by permission, Elsevier.] page 168
• Figure 7.8: A configuration incompatible with the fact that v₀ or v₄ touch the boundary of B. [Fig. 4 in [DLOS03], by permission, Elsevier.] page 169
• Figure 7.9: The link 4²₁, formed when links e₁ and e₄ both pierce △abc. [Fig. 5 in [DLOS03], by permission, Elsevier.] page 169
• Figure 7.10: Interlocked open, flexible 3- and 4-chains. [Fig. 6 from [DLOS02], by permission, Elsevier.] page 169

• Introduction and Motivation page 171
• Dihedral Motions page 172
• Figure 8.1: A local dihedral motion about edge e. page 172
• Figure 8.2: Dihedral motion about e viewed as constrained by nested cylinders. page 172

• Minimum Flat Span page 173
• Figure 8.3: A chain whose minimum span is 5/6; 2 + 4 + 6 = 1 + 8 + 3 is the corresponding partition of S. page 173
• Maximum Flat Span page 174
• Figure 8.4: Internal turns of 10° + 80° − 20° + 30° − 40° − 60° result in parallel end links, corresponding to the 1 + 8 + 3 = 2 + 4 + 6 partition. (Not to scale: the dots indicate omissions.) page 174
• Failure in 3D page 174
• Open Problem 8.1: Extreme Span in 3D page 174
• Figure 8.5: Four flat configurations of the same chain. page 175
• Figure 8.6: Chain achieving the maximum span in 3D is shown dark; dashed e′₁ and e′₄ edges achieve the maximum span in 2D. (a) View orthogonal to flat state, corresponding to Figure 8.5(a); (b) Oblique view. page 175

• Nonplanar chains page 176
• Figure 8.7: This fixed-angle 4-chain cannot be flattened, although if all joints are flexible it is not locked. Light colored circles constrain positions of v₀ and v₄. page 176
• Flattening NP-Hard page 177
• Figure 8.8: The “key” e_n fits in the “lock” if and only if S has a partition. page 177

• Figure 8.9: (a) and (b) Flat embeddings of the lock chain; (c) and (d) self-crossing configurations. page 178
• Table 8.1: Summary of known results. ‘Unit’ means with unit link lengths; a ‘monotone state’ is a planar, strictly monotone configuration; α represents the joint angles. page 179
• Open Problem 8.2: Flat-state Connectivity of Open Chains page 179

• Figure 8.10: Two flat states of an orthogonal tree. The four edges incident to x are the only ones not rigid, permitting dihedral motions. page 180
• Figure 8.11: The a- and c-branches collide when rotated above. Here the linkage is drawn with |aa₁| = |cc₁| and |bb₁| = |dd₁|. page 181
• Figure 8.12: The a- and b-branches collide when rotated above. page 182

• Figure 8.13: With the additions of the ropes R and S underneath, the a-chain is not linked with the b-chain in (a), but is linked in (b). page 183
• Figure 8.14: An orthogonal graph linkage that is flat-state disconnected. page 183
• Open Problem 8.3: Flat-state Connectivity of Orthogonal Trees page 184

• Figure 8.15: (a) Lifting edges e₁=(v₀, v₁) and e₂=(v₁, v₂): a, b, c. (b) Lifting edges e₃ and e₄: d, e, f. page 185

• Figure 8.16: (a) A chain that fails to be convex (v₀ is not on the hull); (b) |v′₀−v′_n| < |v₀−v_n|. page 187
• Figure 8.17: Opening C while keeping v_k fixed and highest. page 187
• Figure 8.18: (a) Angles between rays and x-axis; (b) Cosine function. page 188

• Figure 8.19: Reconfigurations of convex chain A (red) to B (blue) satisfying Equation 8.2. In each case, the forbidden disk is shown. [Based on Fig. 8 of [O'R00c].] page 190
• Figure 8.20: All b_i + 1 on the cone have the same turn angle at b_i. page 191

• Figure 9.1: The ribosome R in cross-section. The protein is created in tunnel t and emerges at x. [Fig. 1 in [DLO06], by permission, Springer.] page 194

• Figure 9.2: The chain is produced in C_α, and emerges at the origin into the complimentary cone B_α below the xy-plane. [Fig. 2 in [DLO06], by permission, Springer.] page 195
• Figure 9.3: Notation for a configuration Q. [Fig. 3 in [DLO06], by permission, Springer.] page 195

• Figure 9.4: Production of e₀ and e₁ during t ∈ [t₀, t₁]. [Fig. 4 in [DLO06], by permission, Springer.] page 196

• Figure 9.5: A chain in its α-CCC configuration.Here θ_i=π/4 for all i. [Fig. 7 in [DLO06], by permission, Springer.] page 198

• Figure 9.7: (a) The knitting needles; (b) A locked, fixed-angle, unit chain. page 200

• Open Problem 9.1: Locked Unit Chains in 3D? page 201
• Open Problem 9.2: Locked Length Ratio page 201
• Open Problem 9.3: Locked Fixed-angle Chains page 201
• Open Problem 9.4: Locked Unit Trees in 3D? page 201

• Introduction page 202
• PRM History page 202
• Figure 9.8: Four configurations of an 8-dof robot arm. page 204
• Further Development of PRM page 205
• Amato Research page 205
• Figure 9.9: Folding snapshots of a polypeptide chain with 10 Alanine amino acids [SA01, Fig. 2]. page 205

• Introduction page 206
• Model page 206
• Figure 9.10: A four-frame animation of a protein folding continuously according to forces based on the HP model plus additional forces to avoid collisions. [Based on [ISK99, Fig. 10B].] page 207

• Open Problem 9.5: Complexity of Protein Folding in Other Lattices page 209

• Open Problem 9.6: PTAS for Protein Folding page 209
• Figure 9.11: Gadgets used in the ⅓-approximation algorithm of [New02]. Based on Figs. 5 and 6 of [New02]. page 210

• Protein design page 210
• Unique foldings page 211
• Closed chains page 211
• Figure 9.12: The uniquely foldable closed chains and their optimal foldings. page 212
• Open chains page 212
• Figure 9.13: In an optimal folding of Figure 9.12, (a) there can be no contacts external to the closed chain, (b) the graph of contacts can have no cycles, (c) the graph of contacts must be a complete path, and (d) these contacts decompose the chain into uniquely embeddable squares. page 213
• Figure 9.14: The uniquely and doubly foldable open chains and their optimal foldings. page 213
• Open Problem 9.7: Protein Design page 214

• Figure 10.1: The classic crane crease pattern and corresponding flat origami. page 220

• Time Continuity of Geometry page 226

• Figure 11.1: Lang's fractal flat folded state of a 1D piece of paper, based on the Cantor set. The length of the folded state is one third of the length of the piece of paper. [Personal communication from Robert Lang, Aug. 2004.] page 227

• Figure 11.2: Two candidate folded states f with the same geometric image f(P) (a). The f in (b) is invalid, and the f in (c) is valid. page 228
• Figure 11.3: λ(p, q) cannot always be defined in a continuous way when q is a crease point: points near q have opposite orientations in the folded state, so λ(p + ε, q±ε) = ±1 for ε > 0 small. page 229

• Figure 11.4: Antisymmetry of λ. page 230

• Figure 11.5: Transitivity of λ. page 231

• Figure 11.6: The interval (q^−, q^+) containing q and mapping via f to the interior of in the ε-radius circle C splits C into two halves: C^+ and C^−. page 232
• Figure 11.7: Valid local situations in which neither p^+ nor p^− map via f to the same location as q^+ or q^−. In (a) and (b), p and q are crease points. In (c), p and q are smooth. page 233

• Figure 11.8: Valid local situations in which one or more pairs from {p^+, p^ − } × {q^+, q^ − } are collocated according to f. In (a), exactly one pair is collocated. In (b–e), exactly two pairs are collocated. In (f–h), all four points collocate. page 235

• Time Continuity of Order page 236

• Figure 11.9: (a) The shortest path between two points measured on a square piece of paper. (b) A simple (semifree) folded state and the shortest path between the same points in that folding. page 239

• Time Continuity of Order page 242
• Figure 11.10: (a) The image of f_t + ε applied to B_p. (b–c) Two possible curves yielding the same image. Note that points interior to the four quadrants have opposite winding numbers in (b) and in (c). page 243

• Figure 11.11: Illustration of the proof of Lemma 11.6.1. page 245
• Figure 11.12: Rolling a triangle P into a subtriangle T. page 246

• Figure 11.13: The construction of a folding motion of P into a folded state (f, λ) (not to scale). S = f(P) is the image of the folded state. w is the continuous folding motion that wraps T onto its home f(T) on S. r is the motion that takes P to a flat folded state T within the plane. (Origami bird is based on a design by L. Zamiatina.) page 247

• Figure 12.1: Two simple types of crease patterns: (a) parallel creases and (b) creases incident to a single vertex. page 250
• Figure 12.2: A 1D piece of paper with three different mountain-valley patterns. (a–b) are flat foldable; (c) is not. page 251
• Figure 12.3: The two local operations for 1D folds. page 251
• Figure 12.4: The mingling property. Here there is mingling at the c_i end but not the c_j end of the sequence. page 252
• Figure 12.5: The innermost edge of a spiral cannot be longer than the adjacent edge. page 253
• Figure 12.6: A mingling mountain-valley pattern that when crimped is no longer mingling. page 254
• Figure 12.7: Moving layers of paper out of the zig-zag formed by a crimp (c_i, c_i + 1), highlighted in bold. page 255

• Figure 12.8: Flat foldings of single-vertex crease patterns. (a) Flat paper: σ = 360°. (b) Cone: σ = 270°. The two straight edges are glued together. (c) Negative curvature: σ = 420°. page 257
• Figure 12.9: Constructing a mountain-valley assignment for a flat-foldable single-vertex crease pattern with angles 31° + 39° + 41° + 58° + 108° + 83° = 360°, which have alternating sum 31° − 39° + 41° − 58° + 108° − 83° = 0°. Top: Cutting an arbitrary edge and folding alternately mountain and valley. Middle: Cutting at an edge that folds to an extreme. Bottom: Regluing the cut. page 259

• Figure 12.10: (a) The wrapping of the linear flat folding (b) [not to scale]. The ends are separated by 360° = 2π, joined after wrapping once by the red arc. This single vertex has 16π of paper incident to it. The resulting flat folding has M = V = 3. page 261
• Figure 12.11: The rolling process that produces the wrapping shown in Figure 12.10 [to scale]. page 261
• Figure 12.12: If an angle is a strict local minimum, then the two incident creases must have opposite orientation or else the folding is forced to self-intersect, no matter what the choice of overlap order. page 263
• Figure 12.13: Closing a chain of equal angles surrounded by strictly larger angles. page 265

• Figure 12.14: The crease pattern and fold angles φ_i of a corner fold. page 270
• Figure 12.15: An unfoldable crease pattern that satisfies the necessary condition of Theorem 12.2.14. Dotted lines denote self-intersections in the attempted folded state. page 272
• Open Problem 12.1: 3D Single-Vertex Fold page 272

• Figure 12.16: Flexing of a spherical quadrilateral composed of (90°, 90°, 45°, 45°) arcs. page 273

• Figure 13.1: Examples of determining local foldability. The symbol ‘≠’ denotes two oppositely paired creases, and ‘=’ denotes an equal pairing. page 277
• Figure 13.2: All possible pairings of creases at a nongeneric vertex with several equal angles. page 277

• Figure 13.3: A wire carries a Boolean signal based on whether the crease on the left is a valley, where the left side is determined by the orientation denoted by an arrow. page 280

• Figure 13.4: Not-All-Equal clause gadget: the crease pattern, the local equal/opposite pairing, all valid mountain-valley assignments up to rotational symmetry, an invalid mountain-valley assignment, and a shadow of the intersection that arises. page 281
• Figure 13.5: Reflector gadget: the crease pattern with parameter 90° ≤ θ < 180°, the local equal/opposite pairing, and all valid mountain-valley assignments up to inversion of the central isosceles triangle. page 282

• Figure 13.6: Crossover gadgets: crease pattern, two valid mountain-valley assignments, and two invalid mountain-valley assignments. page 283
• Figure 13.7: Overview of the reduction from All-Positive Not-All-Equal 3-Satisfiability to flat foldability of a crease pattern. page 284

• Open Problem 14.1: Map Folding page 287
• Figure 14.1: (a) A map-folding puzzle. (b) A crude depiction of a solution, with several squares labeled (lightly shaded labels are facing away from viewer). page 288

• Figure 14.2: (a) A crease pattern foldable by some-layers simple folds, but not by one- or all-layers simple folds. (b) Top view of a flat folding. page 289

• Figure 14.3: An all-layers fold of 1D paper. page 290

• Figure 14.4: Folding a 2 × 4 map via a sequence of three all-layers simple folds. page 291

• Figure 14.5: Hardness reduction from partition problem. page 293
• Figure 14.6: Semi-folded staircase confined between y coordinates of P₁ and P₂. page 294

• Open Problem 14.2: Orthogonal Creases page 295
• Open Problem 14.3: Pseudopolynomial-time Map Folding page 295

• Figure 15.1: (a) Polygonal silhouette of a horse. (b) Polygonal two-color pattern of a zebra. (c) Origami zebra folded from a bicolor square of paper, designed by Montroll [Mon91, pp. 94–103]. page 298

• Figure 15.2: Turn gadgets: (a) Sharp turn (>180°); (b) Very sharp turn (>270°); (c) Blunt turn (<180°); (d) (Blunt) turn with overhang. page 299
• Figure 15.3: Color-reversal gadget. page 299

• Figure 15.4: Covering a triangle T_i by zig-zagging parallel to the edge e_i incident to the next triangle T_i + 1, choosing the initial direction so that we end at the vertex v_i + 1 opposite the next edge e_i + 1. page 300
• Figure 15.5: Silhouette of turn gadget needed to effect a turn at vertex v between two triangle zig-zags. page 300
• Figure 15.6: First three folds in “hiding” a polygon P of paper underneath a convex polygon C, without disturbing a specified edge e. page 301

• Figure 15.7: Hamiltonian refinement of a triangulation. page 302
• Figure 15.8: A simple example of a reflex region between seams in a flat folding. page 302
• Open Problem 15.1: Seam Patterns page 303

• Open Problem 15.2: Efficient Silhouettes and Wrapping page 303

• Figure 15.9: Folding of a unit square to largest possible cube (side length √2/4) from [CJL01]. The white faces are tucked underneath the surface, leaving only the shaded faces visible. Dashed segments are valley folds; solid segments are mountain folds. page 304

• Table 15.1: Ratios of checkerboard side length to original paper side length for best known foldings and the limit predicted by color-reversal perimeter. page 305
• Figure 15.10: Shortest possible Eulerian tours that visit all color-reversal edges: (a) k odd: 2k(k − 1) + 2(k − 1) edges; (b) k even: 2k(k − 1) + 2k edges. page 306
• Figure 15.11: The color-reversal pattern of a 2 × 2 checkerboard can be achieved without decreasing the size of the square, but two cells of the checkerboard are half absent. page 306

• Figure 16.1: Lang's Scorpion varileg, opus 379. page 308

• Figure 16.2: The six standard origami bases. page 309
• Figure 16.3: Folding a bird base, and “shaping” it into a crane. page 309
• Figure 16.4: Uniaxial base for a lizard with four legs, head, body, and tail. The bottom of the base is placed against the xy-plane, but drawn here above to illustrate the projection. [Based on [Lan98, Fig. 5.1].] page 310

• Figure 16.5: The metric tree that should be specified as the desired shadow tree to obtain the base in Figure 16.4. [Based on [Lan98, Fig. 5.2].] page 312

• Figure 16.6: Illustration of the proof of Lemma 16.4.2: (a) The cross point x of two active paths on the paper must derive from a single point x₁=x₂ on the paths, or else the path (x₁, x₂) violates Lemma 16.4.1. (b) Crossing active paths violate Lemma 16.4.1 on the cross-path (v₁, w₂). page 314
• Figure 16.7: A likely optimal mapping of leaves from the shadow tree in Figure 16.5 to points on a square of paper. Line segments denote active paths or paper boundary. [Based on [Lan98, Fig. 5.6].] page 315

• Figure 16.8: Satisfying placements of leaf w lie along ellipse E. The two points labeled w correspond to the subdivision point x. page 317

• Figure 16.9: Location of all vertices of the shadow tree on a square of paper, using the leaf mapping from Figure 16.7. Line segments denote active paths or paper boundary. [Based on [Lan98, Fig. 5.7].] page 319

• Figure 16.10: Subtrees induced by the convex decomposition of Figure 16.9, each solved by a universal molecule. [Based on [Lan98, Fig. 5.8].] page 320
• Figure 16.11: (a) Convex polygon shrinking: original and two snapshots. (b) Corresponding slices in 3D. (c) Shadow trees: original plus the two corresponding trimmed trees. page 322
• Figure 16.12: The crease pattern and resulting uniaxial base with the tree specified in Figure 16.4 by filling universal molecules into the active polygons in Figure 16.9. [Based on [Lan98, Fig. 5.18].] page 323

• Figure 17.1: How to fold a square of paper so that one cut makes a regular five-pointed star. page 325
• History page 325
• Figure 17.2: Examples of cut patterns achievable by folding and one complete straight cut (via the straight skeleton method). All but the swan starts by folding in half along the line of symmetry. [Based partly on [DDL00, Fig. 3–4].] page 326
• Result page 327

• Figure 17.3: One fold aligns two graph edges. page 328

• Figure 17.4: Shrinking a face of the graph to form the straight skeleton. Graph edges are thick; shrunken copies are dashed; skeleton edges are thin and solid. page 329
• Figure 17.5: The straight skeleton of a turtle. Graph edges are thick; skeleton edges are thin. page 329
• Figure 17.6: The behavior of the shrinking process (dotted) and the straight skeleton (thin) locally around a degree-0 or degree-1 cut vertex (thick). page 330

• Figure 17.7: The straight skeleton (thin solid) and all perpendiculars (dashed) for the turtle from Figure 17.5. page 331

• Figure 17.8: Mountain-valley pattern for the turtle crease pattern from Figure 17.7, slightly simplified. page 332

• Figure 17.9: A simple example of spiraling. [Based on [DDL00, Fig. 8].] page 333

• Figure 17.10: Example of dense behavior. Top shows plane graph (thick), straight skeleton (thin), and beginning of all perpendiculars (dashed). Bottom shows the progression of one perpendicular path, never ending. page 334
• Figure 17.11: A 3-coloring of the corridors resulting from the turtle. page 335
• Figure 17.12: The four possible shapes of corridors. [Based on [DDL00, Fig. 9].] page 335
• Figure 17.13: (a) Crease pattern for a turtle with perpendiculars labeled. (b) The shaded corridor folded into an accordion. (c) The shadow tree. page 336

• Figure 17.14: Flattening the tree from Figure 17.13. page 337

• Figure 17.15: (a) Graph, a nonconvex quadrangle; (b) Offsetting by ±ε; (c) Disk packing; (c) Decomposition into triangles and quadrangles. page 340
• Figure 17.16: Schematic diagram of the flat folding of a polygon P, with exterior (blue) and interior (sand). The ribbon offset ±ε around P is shown pink. (a) before and (b) after sink folding. page 340

• Figure 17.17: Triangle and quadrangle molecules: (a) crease patterns; (b) folded states; (c) overhead views. page 342

• Figure 17.18: (a) Square polygon; (b) Disk packing and ribbon expanding the polygon (now dashed) by ±ε. page 343

• Figure 17.19: Cutting open a spanning forest to produce a molecule tree (blue), assigning mountain creases (red), and the ordering (green) of the molecule edges (thick dashed edges). page 344

• Figure 17.20: (a) A 7-arm starfish with quarter planes; (b) Two views of nested underneath gluings of starfish arms, from above (left) and below (right) the base plane. page 346

• Figure 17.21: (a) Molecule tree from Fig. 17.19, labeled: abcd is the central square; (b) Depiction of side-view of a partial folding; arrows underneath indicate later gluings to resuture cut edges. page 347
• Figure 17.22: Creasing the partial folding in Fig. 17.21 along the central red/blue molecule path, turns each molecule into a starfish, here shown in an overhead view, separated for clarity (dashed lines connect repeated segments). Note the left/right asymmetry at the four corner molecules, A, C, E, and G. page 348

• Figure 17.23: Sink-folding the starfish of a square molecule: (a) crease pattern; (b) folded state; (c) nested M/V creases for generic molecules (not all creases shown). page 350

• Figure 17.24: (a) A collection of polygons including all three generalizations; (b) The corresponding region-boundary tree. page 352
• Figure 17.25: Region-boundary trees: (a) One polygon; (b) Several disjoint, nonnested polygons; (c) One polygon with two disjoint polygons nested inside (corresponding to Fig. 17.26(a) with x = P, y = P₁, z = P₂). page 353

• Figure 17.26: Schematic diagram of the flat folding for a polygon P containing two polygons P₁ and P₂: (a). (b) before and (c) after sink folding. The ribbon offsets ±ε around P, P₁, and P₂ are shown pink. Cf. Fig. 17.16. page 355

• Figure 18.1: Flattening a cereal box. page 357
• Open Problem 18.1: Continuous Flattening page 358

• Figure 18.2: Solving the 2D polygon-flattening problem via the 2D fold-and-cut problem. page 359

• Open Problem 18.2: Flattening Higher Genus page 360

• Figure 18.3: The 3D straight skeleton of a pyramid, and the subdivision of its surface resulting from dropping perpendiculars. page 361
• Figure 18.4: Extracting the gluing in 2D polygon-flattening from perpendiculars in the 2D fold-and-cut problem. page 362
• Open Problem 18.3: Flattening via Straight Skeleton page 362
• Figure 18.5: Flattening the skeletal collapse of a pyramid. page 363

• Figure 19.1: Abe's method for trisecting an angle using origami. page 365

• Figure 19.2: Folding a square to create two new points. page 366
• Figure 19.3: Huzita's six axioms. Solid lines are existing lines; dashed lines are the new creases. page 366
• Figure 19.4: Abe's Trisection analyzed. page 367
• Box 19.1: Abe's Trisection page 368
• Figure 19.5: Huzita's Axioms A5 and A6. page 368

• Figure 19.6: Hatori's Axiom A7. page 369

• Figure 19.7: Messer's method for doubling a cube using origami. page 370

• Figure 19.8: Simulating an arbitrary linkage with n bars by folding n rulers. page 372

• Figure 20.1: Model of a “tall” grocery shopping bag. The standard flat state uses valley folds along the blue creases, and mountain folds along the red creases.. page 376

• Tessellations page 377
• Pleated hyperbolic paraboloids page 377
• Figure 20.2: Folding a hyperbolic paraboloid. page 377
• Figure 20.3: An origami design studied at the Bauhaus in the 1920s. page 378
• Figure 20.4: Two views of a curved origami construction designed with Martin Demaine. page 378

• Beyond page 379
• Figure 20.5: Three David Huffman constructions. [Credits: E. Huffman & T. Grant; Permission, E. Huffman, 2005] page 380

• Figure 21.1: The title page of Dürer's book: “Underweysung der messung…im jar MDXXV.” page 384
• Figure 21.2: Dürer's net (left) for a cuboctahedron (right). page 384
• Figure 21.3: Dürer's net for a truncated icosahedron. page 385
• Open Problem 21.1: Edge-Unfolding Convex Polyhedra page 386

• Figure 21.4: The curvature at a point is 1/r, where r is the radius of the osculating circle. page 387
• Principal Curvatures page 387
• Gaussian Curvature page 387
• Curvature and Normals page 387
• Figure 21.5: Spinning a plane about N through p ∈ S yields the principal curvatures at p. The curvature of the curves for plane A and B are positive at p, but negative for plane C. page 388
• Curvature and Perimeter and Area page 388

• Figure 22.1: Lundström Design vinyl phone. [Lundström Design, by permission.] page 392

• General Unfoldings page 392
• Number of Pieces page 392
• Figure 22.2: The star unfolding of a polyhedron of n = 18 vertices. page 393
• Open Problem 22.1: Fewest Nets page 393
• Overlap Penetration page 394
• Figure 22.3: R is a region on the blue section that unfolds on top of the purple section. The cut curve γ is shown in red; the xy segment that determines the penetration ω is shown in blue. page 395
• Open Problem 22.2: Overlap Penetration page 395
• Nonconvex Polyhedra page 395
• Figure 22.4: Orthogonal polyhedra with no edge unfoldings. [Based on Fig. 9 of [BDD⁺98b].] page 396
• Simple Polygon page 396

• Figure 22.5: Four nonsimple polygons. In (b) the cut is intended to have zero width. page 397
• Figure 22.6: (a,b,c) Three views of polyhedron; (d) Overhead view; (e) Unfolding. Based on Figure 2 in [BDE⁺03] page 398
• Table 22.1: Status of main questions concerning nonoverlapping unfoldings. page 398

• Figure 22.7: Unfoldings of the 13 Archimedean solids. Clockwise, starting at 1 o'clock: Great Rhombicuboctahedron, Truncated Dodecahedron, Small Rhombicuboctahedron, Small Rhombicosidodecahedron, Snub Cube, Cuboctahedron, Truncated Tetrahedron, Snub Dodecahedron, Great Rhombicosidodecahedron, Truncated Octahedron, Icosidodecahedron, Truncated Cube; Center: Truncated Icosahedron. Computed by Eric Weisstein's code Archimedean.m, and PolyhedronOperations.m available at http://www.mathworld.wolfram.com/packages/. page 400
• Figure 22.8: All faces are colored blue on the outside and red on the inside. (a) A flat doubly covered quadrilateral. (b) Unfolding from cutting path (a, b, c, d). (c) Unfolding from cutting (a, c, d, b). page 401
• Figure 22.9: (a) Cube with corner truncated; (b) Unfolding. Based on [NF93]. page 402

• Figure 22.10: Each point in this graph represents an average of 5 randomly generated polyhedra whose vertices lie on a sphere, and the percentage of 1000 randomly selected unfoldings of each which overlap. After Fig. 2.12 in [Sch89, p.30]. page 403
• Figure 22.11: rightmost-ascending-edge-unfold, Figure 40c in [Sch97]. page 403
• Figure 22.12: normal-order-unfold Figure 42b in [Sch97]. Overlap circled. page 403

• Figure 22.13: steepest-edge-unfold: Figure 35 in [Sch97]. page 405
• Figure 22.14: flat-spanning-tree-unfold Figure 38 in [Sch97]. page 405
• Figure 22.15: An open triangulated hat that cannot be edge-unfolded. page 406
• Figure 22.16: Both possible cut trees leave one spike base vertex (marked) with only one spike face (shaded) removed. page 407
• Figure 22.17: Two views of an ununfoldable triangulated polyhedron. page 408
• Figure 22.18: Possible restrictions of a cut tree to one hat. page 408
• Figure 22.19: A general unfolding of a spiked tetrahedron. page 409
• Open Problem 22.3: General Nonoverlapping Unfolding of Polyhedra page 409
• Figure 22.20: An open surface that has no general unfolding to a net. page 410

• Figure 22.21: A prism. page 410
• Figure 22.22: A prismoid. The base B is a regular octagon. page 410

• Figure 22.23: A nonoverlapping volcano unfolding of the prismoid of Fig. 22.22. page 411
• Figure 22.24: A volcano unfolding of a prismoid (not shown) that overlaps. page 412
• Figure 22.25: (a) A nearly flat prismatoid, viewed from above, cut tree in red; (b) Overlapping volcano unfolding. Primes indicate unfolded items. page 413
• Figure 22.26: Volcano unfolding of a smooth prismatoid, the convex hull of an ellipse top A twisted with respect to a rounded quadrilateral base B. page 413

• Figure 22.27: Front and back view of the same dome. The projection of the apex onto the base plane is shown for perspective. page 414
• Figure 22.28: (a) Outerplanar dual graph of faces; (b) Extension of incident faces A and B to encompass C; (c) Proof of Lemma 22.5.4: two empty sectors xz and yz are shown. page 415
• Figure 22.29: An impossible dome overlap in which no pair of adjacent faces overlap. page 416

• Figure 22.30: (a) The situation after reduction to n − 1 faces and return to n faces; (b) Perpendicular bisector of xz to the “wrong side” of c. page 418
• Figure 22.31: Unfolding of dome in Figure 22.27. page 419
• Figure 22.32: Sector nesting (Lemma 22.5.4) for unfolding in Figure 22.31. page 419
• Figure 22.33: Two nonstrictly-convex nets of a regular tetrahedron. [After Fig. 1 of [She75].] page 420

• Orthostacks page 420
• Figure 22.34: (a) A four-piece orthostack: S = E₀ ∪ E₁ ∪ E₂ ∪ E₃. (b) Refined orthostack, highlighting the band B₃, and showing only the additional edges needed by the algorithm. page 421
• Figure 22.35: One unit of a generic orthostack unfolding. The Z_i faces are distributed into the two regions indicated. page 421
• Orthotubes page 422
• Figure 22.36: (a) Orthotube; (b) Gridded orthotube. page 422
• Open Problem 22.4: Edge-Unfolding Polyhedra Built From Cubes page 422

• Open Problem 22.5: Edge-Unfolding for Non-acute Faces page 423
• Open Problem 22.6: Edge-Unfolding for Non-obtuse Triangulations page 423
• Open Problem 22.7: Vertex Grid Refinement for Orthogonal Polyhedra page 423
• Open Problem 22.8: Refinement for Convex Polyhedra page 424
• Figure 22.37: 1-to-4 refinement. page 424

• Figure 22.38: Six frames from an unfolding of a cuboctahedron computed by Matthew Chadwick. (Scale varies frame to frame.) Note that two faces interpenetrate in the second and third frames. http://celeriac.net/unfolder/. page 425
• Figure 22.39: Vertex unfoldings of random convex polyhedra. The number of triangles is indicated between the polyhedron and the unfolding (which are not shown to the same scale). The unfoldings were constructed using an earlier, less general algorithm [DEE⁺01] [implemented with Dessislava Michaylova]. page 427
• Figure 22.40: Laying out face paths in vertical strips: (a) cube; (b) 16-face convex polyhedron. page 428
• Figure 22.41: This trapezoid cannot be laid out in a strip with v_i and v_i + 1 horizontally extreme. page 429
• Figure 22.42: Vertex-unfolding the top four triangles of the regular octahedron and making the connections planar. page 429
• Figure 22.43: Tree manifold (a) to scaffold (b) to connected scaffold (c) to face cycle (d) to strip layout (e). The layout is based on a different face path than used in Figure 24.22(a). [Figure by Jeff Erickson, Fig. 4 in [DEE⁺03], by permission, Marcel Dekker.] page 430
• Figure 22.44: (a) A truncated cube; (b) its eight triangle and six octagon faces. page 431
• Open Problem 22.9: Vertex Unfolding page 431

• Steinitz's Theorem page 433
• Pieces of Information page 434
• Minkowski's Theorem page 434
• Figure 23.1: (a) A polyhedron with area-weighted face normals; (b) Normals translated to origin. page 435

• Figure 23.2: Two different polyhedra with the same facial structure. page 436

• Figure 23.3: Two views of the spherical polygon Q produced by intersecting a polyhedron in the neighborhood of a vertex v with a sphere S_v centered on v. page 437
• Figure 23.4: The spherical polygon Q. (a) All angles {+, 0}: the subchain C opens; (b) Angles partition into {+, 0} and {−, 0}: the subchain C^+ opens. page 438
• Figure 23.5: A +/− sign change around v is also a sign change in a traversal of the boundary of f. page 440

• Figure 23.6: Half of a regular octahedron, flexing. page 441

• Table 23.1: Coordinates of vertices in Figure 23.7. page 441

• Figure 23.7: Two views of one of Bricard's flexible octahedra. See http://www.fucg.org/III for a (rigid) 3D Java applet model. page 442

• Figure 23.8: Unfolding of Steffen's flexible polyhedron. Dashes are valley folds, dash-dots represent mountain folds. Numbers indicate (integer!) edge lengths, letters gluing instructions. page 443
• Figure 23.9: Steffen's flexible polyhedron from one point of view: Hidden surfaces removed (left); Hidden lines shown dashed (right). page 444

• Convex Polyhedral Metrics page 445
• Alexandrov Gluing page 445
• Relation to Cauchy Rigidity page 446

• Cauchy to Alexandrov page 447
• Figure 23.10: Shortest paths between all pairs of vertices on a convex polyhedron [Fig. 1 in [KO00]]. page 447
• Sketch of Existence Proof page 447
• Figure 23.11: (a) Two copies of A = 60° flatten α; (b) Two copies of θ = 30° flatten β. page 448

• Figure 23.12: Based on Figure 6.49 in [PW01, p. 401], by permission. page 450
• Figure 23.13: D-form (b) constructed from two “racetracks” (a). page 450
• Figure 23.14: A pita-form. page 450
• Open Problem 23.1: D-forms and Pita-Forms page 451

• Figure 23.15: A row of “house” polyhedra. (a) 11111111; (b) 10100110. page 453
• Figure 23.16: Tetrahedron T determining the unknown diagonal d. page 454
• Open Problem 23.2: Practical Algorithm for Cauchy Rigidity page 455

• Figure 24.1: Two views of the shortest paths from a source point x to all n = 100 vertices of a convex polyhedron; x is obscured in the “back-view” (b). This shortest paths are shown lifted slightly from the surface to ensure their visibility. [Computations from [Xu96].] page 459
• Figure 24.2: Pyramid, front (a) and side (b) view. Shortest paths to five vertices from source x are shown solid; the cut locus is dashed. Coordinates of vertices are (±1, ±1, 0) for v₁, v₂, v₃, v₄, and v₀=(0, 0, 4); x = (0, 3/4, 1). [Based on Fig. 1 in [AAOS97].] page 459
• Figure 24.3: Source unfolding for the example in Figure 24.2. Shortest paths to vertices are solid, polyhedron edges are lightly dashed, and the cut locus is the dashed outer boundary. [Based on Fig. 3 in [AAOS97].] page 460
• Figure 24.4: (a,c) Shortest paths through a vertex; (b,d) Shortcuts after rotating faces. page 462
• Figure 24.5: Shortest paths just left (a) and right (b) of v meet at an edge of T_x incident to v. page 463

• Figure 24.6: A polyhedron whose n = 99 vertices lie on the surface of an ellipsoid. [Fig. 7 in [KO00].] page 464
• Figure 24.7: An unfolding of paths from x to an interval I; z is the closest point to x among all the points of I. page 465

• Figure 24.8: Terrain of n = 2140 vertices and F = 4274 faces. Top: oblique view; bottom: overhead view. [Based on Fig. 11 in [KO00].] page 467
• Figure 24.9: Two views of a wireframe cube: n = 160 (F = 336) [Based on Fig. 14 in [KO00].] page 468
• Figure 24.10: [Ale50, p. 181] page 468
• Figure 24.11: Construction of the star unfolding corresponding to Fig. 24.2. (a) The superimposed dashed edges show the “natural” unfolding obtained by cutting along the four edges incident to v₀. The A, B, C, D, and E labels indicate portions of the star unfolding derived from those faces. (b) The cut locus displayed inside the star unfolding. [Based on Figs. 5 and 6 in [AAOS97].] page 469
• Figure 24.12: Four star unfoldings: n = 13, 13, 36, 42 vertices, left to right, top to bottom. The core is shaded darker in each figure. [Code written by Julie DiBiase and Stacia Wyman.] page 470

• Figure 24.13: A polyhedron (a) whose star unfolding (b) from x overlaps. Several edge lengths and face angles are detailed, as well as a few critical computations. page 472
• Figure 24.14: A polyhedron with one vertex of negative curvature. The dimensions have been chosen so that the vertices at the small base regular octagon have curvature exactly zero. page 473
• Box 24.1: Voronoi Diagrams page 474
• Figure 24.15: A Voronoi diagram of 40 sites, clipped to a rectangular region. page 474
• Figure 24.16: Shortest paths to all vertices of a polyhedral cylinder. [Fig. 6 in [KO00].] page 475
• Open Problem 24.1: Star Unfolding of Smooth Surfaces page 475

• Geodesics page 476
• Quasigeodesics page 476
• Figure 24.17: (a) Any continuation of the segment xv angularly between vr and vt is a quasigeodesic; (b) Rotation of faces unfolds vy collinear with xv. page 477
• The Lyusternik-Schnirelmann Theorem page 478
• Figure 24.18: Two views of a closed quasigeodesic on a convex polyhedron of 21 vertices, 38 faces, and 57 edges. (The marked vertex is the same in both views.) page 478
• Closed Quasigeodesics on Polyhedra page 478
• Open Problem 24.2: Closed Quasigeodesics page 478

• Figure 24.19: The faces F crossed by the closed quasigeodesic in Figure 24.18 (from a different viewpoint). The quasigeodesic passes through the marked vertex. page 479
• Open Problem 24.3: Closed Quasigeodesic Edge-Unfolding page 479
• Figure 24.20: Faces cut by a horizontal geodesic unfold with overlap. page 480

• Figure 24.21: (a) A convex polygonal curve C on a polyhedron P; (b) P′: After removal of interior vertices and retriangulation; (c) Development of C from P′ (closed) and from P (open). page 482
• Figure 24.22: (a) Slice curve C = (c₀, c₁, c₂, c₃); (b) its development B. (c) slice curve (c₀, c₁, c₂, c₃, c₄); (d) its development. [Based on Fig. 1 of [O'R03], by permission, Elsevier.] page 483
• Figure 24.23: Q is a slice through a cube P. Angles are shown at corner c_i of Γ = ∂Q. [Based on Fig. 4 of [O'R03], by permission, Elsevier.] page 484
• Figure 24.24: Violation of Theorem 24.5.1. q₁=q₂ is the first point of self-contact; the initial portion of B, up to q₂, is highlighted. [Based on Fig. 3 of [O'R03], by permission, Elsevier.] page 485

• Figure 24.25: (a) A truncated tetrahedron; top and bottom faces removed. (b) An edge-unfolding of the band of side faces obtained by cutting e. [Based on Fig. 5 of [O'R03], by permission, Elsevier.] page 486

• Figure 25.1: A not-foldable polygon. page 488

• Figure 25.2: A perimeter-halving fold of a pentagon. The gluing mappings of vertices v₁ and v₃ are shown. page 489
• Figure 25.3: (a) x varies over (z, v_i) on ∂P; (b) xv_i is the shortest path between those vertices on 𝒫. page 490
• Open Problem 25.1: Folding Polygons to (Nonconvex) Polyhedra page 490

• Figure 25.4: Foldings illustrating aspects of the proof of Lemma 25.1.6. (Paper is exterior to curves shown.) (a) Base case not Alexandrov; (b) Zipping at r₁ produces a new reflex vertex r′₁; (c) Gluing several convex vertices into r₁. page 492

• Figure 25.5: An unfolding of a randomly-generated convex polyhedron. The polyhedron was generated as in [O'R98] and the unfolding produced according to [NF93]. page 493

• Figure 25.6: (a) A polygon that cannot fold to a cube; (b) An unfolding of a cube. page 494
• Figure 25.7: The match {v_i, v_j} creates two subproblems for every possible gluing {e_i, e_k}. page 495

• Figure 25.8: A polygon with two distinct edge-to-edge foldings (based on [She75, Fig. 2].) page 496

• Figure 25.9: The five edge-to-edge foldings of the Latin cross. page 499
• Figure 25.10: Folding the Latin cross to a tetrahedron [DDL⁺99c]. page 500

• Figure 25.11: (a) A polygon, with fold creases shown dashed; (b) A gluing tree T_G corresponding to the crease pattern. page 501
• Figure 25.12: (a) A nonconvex pentagon (creases shown dashed); (b) The corresponding gluing tree; (c) Gluing tree with curvatures (in units of π) marked at each polyhedron vertex. page 502
• Figure 25.13: The polyhedron Q resulting from the folding in Figure 25.12. page 503

• Figure 25.14: (a) An equilateral triangle creased in the interior of each edge; (b) The gluing tree. page 504

• Figure 25.15: A gluing tree with three fold-point leaves, two two forming a rolling belt. page 505
• Figure 25.16: I gluing tree for an L × W rectangle. page 505

• Open Problem 25.2: Finite Number of Foldings page 506

• Figure 25.17: (a) Star polygon P, m = 16, n = 34. (b) Base gluing tree. (c) A gluing tree after several contractions. page 507
• Figure 25.18: Six gluing patterns for a 4-star. Matched edges are indicated by arcs. page 509
• Figure 25.19: Conjectured crease patterns for the first two gluing patterns in the top row of Figure 25.18. [Constructions in Cinderella.] page 510

• Figure 25.20: Mouth angle μ and mouth interval M. page 511
• Figure 25.21: Interval M for v₅ implies sliding of v₄ on e₂. page 511
• Open Problem 25.3: Polynomial-time Folding Decision Algorithm page 514

• Figure 25.23: Foldings to P₁, …, P₆: cube, two quadrilaterals, three tetrahedra. page 516
• Figure 25.24: Foldings to P₇, …, P₁₂: four tetrahedra and two pentahedra. page 517
• Figure 25.25: Foldings to P₁₃, …, P₁₈: a pentahedron, four hexahedra, and an octahedron. page 518
• Figure 25.26: Foldings to P₁₉, …, P₂₃: octahedra. page 519
• Figure 25.27: Computing p₃ for a tetrahedron, in this case P₄ (Figure 25.33), the edge-to-edge tetrahedral folding of the Latin cross (Figure 25.9). page 520

• Figure 25.28: The two combinatorial types of simplicial octahedra. page 521
• Figure 25.29: (a) Two hexahedra with dihedral angles 157.8° and 202.2° along edges e₁ and e₂; (b) The joining of the two to form octahedron P₂₃ of Figure 25.36. page 522

• Figure 25.30: The 23 polyhedra foldable from the Latin cross. page 523

• Figure 25.31: The 23 polyhedra from Figure 25.30 arranged on surface of (an imaginary) sphere. (The connecting lines have no significance; they are included only to enhance the 3D effect.) [Image by Alexandra Berkoff and Sonya Nikolova.]) page 524
• Figure 25.32: The cube and two flat quadrilaterals. (P₂ is the edge-to-edge quadrilateral of Figure 25.10.) page 524
• Figure 25.33: Latin cross tetrahedra. (P₄ is the edge-to-edge tetrahedron of Figure 25.10.) page 525
• Figure 25.34: Latin cross pentahedra. P₁₁ has six vertices and is composed of two triangles and three quadrilaterals. P₁₂ and P₁₃ have five vertices and one quadrilateral face. (P₁₂ is the edge-to-edge pentahedron of Figure 25.10.) page 525
• Figure 25.35: Latin cross hexahedra, all with five vertices, two of degree 3 and three of degree 4. page 525
• Figure 25.36: Latin cross octahedra, each of six vertices. P₁₈, P₁₉, P₂₀, and P₂₁ have two vertices each of degrees 2, 3, and 4, and are composed of three stacked tetrahedra. P₂₂ and P₂₃ have all vertices of degree 4, and are combinatorially equivalent to a regular octahedron. (P₂₃ is the edge-to-edge octahedron of Figure 25.10.) page 526

• Figure 25.37: A hexagon (a) folds via an I gluing tree to a doubly-covered rectangle (b). page 528

• Figure 25.38: (a,b) Flat foldings of an n-gon, n even (n = 8). (c) Flat folding of an n-gon, n odd (n = 7). page 529
• Figure 25.39: Duodecagon, n = 12, x and y are perimeter-halving fold vertices. The dashed lines are (largely) conjectured creases. page 529
• Figure 25.40: Two views of the approximate 3D shape of pita polyhedron folded as per Fig. 25.39. page 530

• Figure 25.41: Creases for a section of a continuum of foldings: as x varies in [0, ½], the polyhedra vary between a flat triangle and a symmetric tetrahedron. (This is half of loop B in Figure 25.43 below.) page 531
• Figure 25.42: The five rolling belts among foldings of a (unit) square. Selected perimeter halving lines for A and D are shown. page 532

• Figure 25.43: Details of all six continuua. Selected crease diagrams and gluing trees are shown. page 534
• Figure 25.44: The six loops arranged in space, sharing common shapes. page 535

• Open Problem 25.4: Volume Maximizing Convex Shape page 535
• Figure 25.45: The maximum volume convex polyhedron foldable from a square. The red line marks the boundary of the square; the two foldpoints are circled. page 536

• Figure 25.46: The topological structure of the polyhedra foldable from an equilateral triangle. Selected foldings are shown. page 537
• Figure 25.47: The space of foldings of the polygon in Figure 25.48. page 538
• Figure 25.48: n = 8, m = 3, ε = 20°. page 539
• Figure 25.49: Two positions of the t rolling belt. (b) corresponds to the | gluing tree. page 540
• Table 25.1: Inventory of possible foldings of a convex polygon. page 540

• Open Problem 25.5: Flat Foldings page 541
• Open Problem 25.6: Fold/Refold Dissections page 542
• Figure 25.50: A polygon (a) that folds to a regular octahedron and to a tetramonohedron (b), the latter using creases x9, x8, x7, 72, y4, y3, y2; x and y are edge midpoints. page 542
• Figure 25.51: A polygon that folds to a regular tetrahedron and to a rectangular box, shown in Figure 25.52. page 543
• Figure 25.52: The box has dimensions 1 × 1 × √3 − ½; the tetrahedron edge length is 2. page 543
• Figure 25.53: (a,b) One polygon that folds to both a 5 × 1 × 1 box, and a 3 × 2 × 1 box; (c,d) A different polygon that folds to both a 8 × 1 × 1 box, and a 5 × 2 × 1 box. page 544
• Bipartite Space of Foldings & Unfoldings page 544

• Figure 25.54: (a) Ω(n²) combinatorial types achieved by rolling the perimeter belt; (b) Only O(n) possible disjoint vv-pairings. page 546
• Figure 25.55: (a) Polygon P; (b) One four fold-point gluing; the fold points are midpoints of edges. The dashed lines indicate tips of front teeth bent over and glued behind. page 547

• Figure 25.56: (a) Geometric cut tree 𝒯_C on the surface of a cube; (b) The corresponding combinatorial cut tree T_C. page 549
• Figure 25.57: (a) Doubly covered rectangle with cut path; x is the midpoint of edge v₁v₄. (b) Unfolding. (c–d): Another cut path and its unfolding. page 550
• Figure 25.58: (a) Polyhedron Q; (b) Unfolding via (red) cut tree T_1001101. page 551
• Figure 25.59: (a) Polyhedron Q, with a cut tree labled T_{⋯0022020100}. (b) Unfolding to polygon P. page 552

• 2D page 554
• Figure 25.60: (a) Orthogonal polygon corresponding to set S = {2, 4, 5, 6, 3, 2, 1, 3}, and partition 2 + 4 + 6 + 1 = 5 + 3 + 2 + 3. (b) Polygon extruded to orthogonal polyhedron. page 554
• 3D page 554

• Figure 25.61: Two views of an nonorthogonal polyhedron composed of rectangular faces. [Fig. 1 from [DO02].] page 555
• Figure 25.62: An orthogonal creased net for the nonorthogonal polyhedron in Figure 25.61. [Based on Fig. 3 of [BCD⁺02].] page 556
• Table 25.2: Do rectangle faces imply 3D orthogonality? page 556

• Figure 25.63: (a) Orthogonal polyhedron; (b) “Backbone” chain of net; (c) Orthogonal creased net for polyhedron. [Based on Figs. 6 and 7 of [BLS05].] page 558

• Figure 26.1: Extruding a linkage into an equivalent collection of polygons (rectangles) hinged together at their edges. page 559

• Open Problem 26.1: Higher-Dimensional Fold-and-Cut page 560
• Open Problem 26.2: Flattening Complexes page 561

• Figure 26.2: Three snapshots of a hypercube unfolding: (a) after rotation by 10°; (b) after 44°; (c) after 90°. [Computations by Patricia Cahn.] page 561

• Figure 26.3: “Corpus Hypercubus”. Salvador Dali, 1955. ©2006 Salvador Dali, Gala-Salvador Dali Foundation / Artists Rights Society, New York. page 562

• Open Problem 26.3: Ridge Unfolding page 564