# Geometric Folding Algorithms: Linkages, Origami, and Polyhedra

## Table of Contents

 VIEW SETTINGS Figures     Tables     Open Problems     Boxes
Chapter 0: Introduction page 11
0.1: Design Problems page 12
0.1.1: I: Kempe Universality page 12
• Figure 0.1: There is a linkage that traces a thin version of this collection of curves. page 12
0.1.2: II: Origami Design page 12
0.1.3: III: Unfolding to Net page 13
• Figure 0.3: A net for the snub cube, drawn by Dürer. page 14
0.2: Foldability Questions page 14
0.2.1: I: Ruler Folding page 14
0.2.2: II: Map Folding page 15
0.2.3: III: Polygon Folding page 15
• 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
Part I: Linkages page 19
Chapter 1: Problem Classification and Examples page 21
• 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
1.1: Classification page 22
• Table 1.1: Classification parameters for 1D linkage problems. page 24
1.2: Applications page 24
1.2.1: Robotics page 24
• Figure 1.2: A six-axis robot arm. [By permission, Forward Thompson Ltd.] page 25
1.2.2: Mechanisms 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
1.2.3: Bending Machines page 27
• 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
1.2.4: Protein Folding page 28
• 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
1.2.5: Mathematical Aesthetics page 29
Chapter 2: Upper and Lower Bounds page 31
2.1: General Algorithms and Upper Bounds page 31
2.1.1: Configuration Space Approach page 31
• Figure 2.1: (a) Arm and obstacles; (b) (θ1, θ2) 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
2.1.1.1: Specialization to Planar Robot Arms page 34
2.1.1.2: Solving Problems with Configuration Spaces page 35
2.1.2: Example: Separation Puzzles page 36
2.2: Lower Bounds page 37
2.2.1: Introduction page 37
• History page 37
• Table 2.1: Lower bounds. “Simple” means non-self-intersecting. page 38
2.2.2: Three Constructions Sketched 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 x1+x3+x4=x2+x5+x6. page 41
• Figure 2.6: (a) Initial configuration. The dashed segment starting from v0 represents a large collection of unit links. The slashes indicate interruptions. Note the tunnel is only 2 + ε units high. (b) Intermediate configuration, when R100 is folded and about to pass through the gap. page 42
• Path Planning page 43
• Universality Theorem page 43
Chapter 3: Planar Linkage Mechanisms page 45
3.1: Straight-line Linkages page 45
3.1.1: Degrees of Freedom page 45
3.1.2: Watt Parallel Motion page 45
• 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
3.1.3: Peaucellier Linkage page 46
• Figure 3.2: Peaucellier linkage. The dark lines show it in one position, the light lines in another. page 47
3.2: Kempe's Universality Theorem page 48
3.2.1: Kempe's Proof page 48
• 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
3.2.2: The Flaw and Repairs page 54
3.2.2.1: Bracing the Parallelogram 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
3.2.2.2: Bracing the Contraparallelogram 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
3.2.3: Recap page 58
• Open Problem 3.1: Continuous Kempe Motion page 59
• Open Problem 3.2: Noncrossing Linkage to Sign Your Name page 59
3.3: Hart's Inversor 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
Chapter 4: Rigid Frameworks page 63
4.1: Brief History page 63
4.2: Rigidity page 63
• Figure 4.1: (a–c): rigid; (d): flexible. In (b), the bars are not joined at the hexagon center. page 64
4.3: Generic Rigidity 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
4.3.1: Laman's Theorem 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
4.3.2: Higher Dimensions page 68
• 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
4.3.3: Henneberg Constructions page 69
• 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
4.3.4: Global Rigidity page 70
• Open Problem 4.3: Realizing Generically Globally Rigid Graphs page 70
4.4: Infinitesimal Rigidity page 71
4.4.1: Infinitesimal Length Constraint page 71
4.4.2: Rigidity Matrix page 72
• Box 4.1: Rigidity Matrix page 73
4.4.3: Connection between Rigidity and Infinitesimal Rigidity page 74
• 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
4.5: Tensegrities page 76
• 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
4.5.1: Infinitesimal Rigidity of Tensegrities page 76
4.5.2: Connection to Linear Programming page 77
4.5.3: Stress page 77
4.5.4: Duality page 78
• 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
4.5.5: Linkages and Tensegrities page 80
4.6: Polyhedral Liftings page 81
• 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
Chapter 5: Reconfiguration of Chains page 83
5.1: Reconfiguration Permitting Intersection page 83
5.1.1: Chain Reachability page 83
5.1.1.1: Connectivity of Configuration Space page 83
• Figure 5.1: An arm/pinned open chain. The angle αi is the turn angle between adjacent links. page 84
5.1.1.2: Annulus page 84
• Figure 5.2: Annulus sum. page 85
• Figure 5.3: The vector sum e1+e2+e3 is independent of the order of the terms. page 86
• Figure 5.4: Inner radius ri=ℓMs. page 86
5.1.1.3: Two-Kinks Theorem page 87
• Figure 5.5: (a) (ℓM=6) > (s = 5); (b) (ℓM=6) < (s = 15); (ℓM=8) ≤ (s′ = 9). page 87
5.1.1.4: Solving a 3-link problem page 88
5.1.2: Turning a Polygon Inside-Out page 88
• 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: ℓ1−ℓ2 and the remainder of the chain are insufficient to span ℓ3. (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 v2 tracking line L to positions v2 and v2. This is not a simple line-tracking motion because the angle at v3 changes nonmonotonically, as indicated by the angle measurements. page 92
5.2: Reconfiguration in Confined Regions page 93
5.2.1: Chains Confined to Circles page 93
• 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 2n/3 disconnected configurations. page 93
• Figure 5.12: (a) The five links have orientations LLRRL; (b) orientations RLLLR. Thus all but L2 are reoriented. page 94
• Figure 5.13: Normal form for the chain shown in Figure 5.12(a). page 94
5.2.2: Chains Confined to Squares page 95
• Figure 5.14: Link L1=(v0, v1) is “stuck” because it cannot reorient to “aim” toward corner c. page 95
5.2.3: Chains Confined to Equilateral Triangles 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
5.3: Reconfiguration without Self-Crossing page 96
• Figure 5.16: “Stuck” chains: (a) x1 > 0.483; (b) x2=0.5; (c) x3 > 0.866. page 97
• Figure 5.17: (a) Left and Right in neighborhood of a vertex; (b) C = (v0, …, v8) does not self-cross, for it stays on the same side of v0v1 both in a neighborhood of v3, and in neighborhoods of v6 and v7. But if v8 is replaced by v8, then C′ = (v0, …, v8) does self-cross. page 97
• Box 5.1: Self-Crossing page 98
5.3.1: 2D: Convex Polygons page 98
• Figure 5.18: The sign sequence (−, +, −, +, −) alternates four times. page 99
• Figure 5.19: The inscribed quadrangle (vi, vj, vk, vl). page 100
• Figure 5.20: Flexing a quadrangle [After Figure 2 in [ADE+01]]. page 100
5.3.2: 2D/3D: Arbitrary Polygons page 101
• Figure 5.21: A planar arc partially lifted into a vertical line. page 102
5.3.2.1: Pocket Flipping 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 vi is increased by a flip. page 105
• Figure 5.26: Red lines indicate the subset relation. Here P0 ⊆ C0 ⊈ P1. page 106
• Box 5.2: Proof Pitfalls page 107
5.3.2.2: Deflations page 107
• Figure 5.27: (a) Original polygon P0, with lengths 3 + 6 = 4 + 5; (b) deflation step; (c) P1; (d) deflation step; (e) P2; (f) deflation step. page 108
• Figure 5.28: An attempted deflation produces a self-crossing polygon. page 109
5.3.2.3: Variations on Flipping 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
5.3.2.4: Arch Algorithms page 111
• Convex Arch Algorithm page 111
• Figure 5.30: vi + 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 vi + 1, the arch is rotated down to the plane Πε; (c) After reconvexification in Πε “absorbs” vi, 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) vi and vj have been lifted slightly, producing a twisted trapezoid vivi − 1vj + 1vj. page 113
• Figure 5.33: The centers of the spheres Sa and Sb are a′ and b′ respectively. The initial and final positions of aa and bb are shown shaded. page 113
5.3.3: 3D: Simple Projection page 114
• Figure 5.34: A 3D polygon that has a simple projection in the plane below. page 114
• Figure 5.35: (a) Step 0: e0 is rotated within Π1 and then into Π2. (b) Step i: The chain translates within Πi. page 115
Chapter 6: Locked Chains page 117
6.1: Introduction page 117
• 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
6.2: History page 119
6.3: Locked Chains in 3D page 120
6.3.1: Locked Open Chains page 120
• 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 (v1, v2, v3, v4). A reconfiguration of v1 to v1 and v0 to v0 illustrates that v1 remains interior and v0 remains exterior to B. page 121
6.3.2: Locked Closed Chains page 122
• Figure 6.4: K2 (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
6.3.3: Chains of Fat Links 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
6.4: No Locked Chains in 4D 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
6.5: Locked Trees in 2D page 126
• Figure 6.9: Locked planar polygonal trees. Points in shaded circles are closer than they appear. page 128
6.6: No Locked Chains in 2D page 129
• 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
6.6.1: Expansiveness and the Connection to Tensegrities page 132
6.6.2: Combinatorial Argument page 133
• 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
6.6.3: Continuous Argument page 138
6.7: Algorithms for Unlocking 2D Chains page 139
6.7.1: Unlocking 2D Chains using Convex Programming page 140
• 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
6.7.2: Unlocking 2D Chains using Pseudotriangulations 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
6.7.3: Unlocking 2D Chains using Energy 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
6.8: Infinitesimally Locked Linkages in 2D 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
6.8.1: Stronger Definitions of 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
6.8.2: Self-Touching Configurations page 152
6.8.3: Connection to Rigidity page 152
6.8.4: Proving Trees Locked page 153
• 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
6.8.5: Other Problems on Self-Touching Linkages page 156
• Open Problem 6.5: Self-touching Chains page 156
6.9: 3D Polygons with a Simple Projection 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) cd rotates about c′. page 160
Chapter 7: Interlocked Chains page 161
• 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
7.1: 2-chains 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
7.2: 3-chains 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
7.3: 4-chains 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 v0 touches B, point v1 must be exterior to B′ by at least R, and therefore v2 and v3 are also exterior to B′. [Fig. 3 in [DLOS03], by permission, Elsevier.] page 168
• Figure 7.8: A configuration incompatible with the fact that v0 or v4 touch the boundary of B. [Fig. 4 in [DLOS03], by permission, Elsevier.] page 169
• Figure 7.9: The link 421, formed when links e1 and e4 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
Chapter 8: Joint-Constrained Motion page 171
8.1: Fixed-Angle Linkages page 171
• 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
8.1.1: Extreme Spans page 173
• 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 e1 and e4 edges achieve the maximum span in 2D. (a) View orthogonal to flat state, corresponding to Figure 8.5(a); (b) Oblique view. page 175
8.1.2: Flattening page 176
• 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 v0 and v4. page 176
• Flattening NP-Hard page 177
• Figure 8.8: The “key” en fits in the “lock” if and only if S has a partition. page 177
8.1.3: Flat-State Connectivity 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
8.1.4: Flat-State Disconnected Linkages page 180
8.1.5: Partially Rigid Orthogonal Tree page 180
• 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 |aa1| = |cc1| and |bb1| = |dd1|. page 181
• Figure 8.12: The a- and b-branches collide when rotated above. page 182
8.1.6: Orthogonal Graph 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
8.1.7: Open Orthogonal Chains page 184
• Figure 8.15: (a) Lifting edges e1=(v0, v1) and e2=(v1, v2): a, b, c. (b) Lifting edges e3 and e4: d, e, f. page 185
8.2: Convex Chains page 186
8.2.1: Cauchy's Arm Lemma page 186
• Figure 8.16: (a) A chain that fails to be convex (v0 is not on the hull); (b) |v0vn| < |v0vn|. page 187
• Figure 8.17: Opening C while keeping vk fixed and highest. page 187
• Figure 8.18: (a) Angles between rays and x-axis; (b) Cosine function. page 188
8.2.2: Uses and Generalizations of Cauchy's Lemma page 188
8.2.3: Straightening Convex Chains page 189
• 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 bi + 1 on the cone have the same turn angle at bi. page 191
Chapter 9: Protein Folding page 193
9.1: Producible Polygonal Protein Chains page 193
• 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
9.1.1: Notation 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
9.1.2: Chain Production page 196
• Figure 9.4: Production of e0 and e1 during t ∈ [t0, t1]. [Fig. 4 in [DLO06], by permission, Springer.] page 196
9.1.3: Main Results page 197
9.1.4: Producible ≡ Flattenable page 197
• Figure 9.5: A chain in its α-CCC configuration.Here θi=π/4 for all i. [Fig. 7 in [DLO06], by permission, Springer.] page 198
9.1.5: Random Chains page 200
• Figure 9.7: (a) The knitting needles; (b) A locked, fixed-angle, unit chain. page 200
9.1.6: Open Problems on Unit Chains page 201
• 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
9.2: Probabilistic Roadmaps page 202
• 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
9.3: HP Model page 206
• 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
9.3.1: NP-completeness page 207
• Open Problem 9.5: Complexity of Protein Folding in Other Lattices page 209
9.3.2: Approximation Algorithms 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
9.3.3: Unique optimal Foldings 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
Part II: Paper page 215
Chapter 10: Introduction page 217
10.2: History of Origami Mathematics page 219
10.3: Terminology page 219
• Figure 10.1: The classic crane crease pattern and corresponding flat origami. page 220
10.4: Overview page 220
Chapter 11: Foundations page 223
11.1: Definitions: Getting Started page 224
11.1.1: Free Folded States of One-Dimensional Paper page 224
11.1.2: Free Folding Motions of One-Dimensional Paper page 225
• Time Continuity of Geometry page 226
11.1.3: Smoothness and Creases of One-Dimensional Paper 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
11.2: Definitions: Folded States of 1D Paper page 227
11.2.1: Order 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
11.2.2: Antisymmetry Condition page 229
• Figure 11.4: Antisymmetry of λ. page 230
11.2.3: Transitivity Condition page 230
11.2.4: Consistency Condition page 230
• Figure 11.5: Transitivity of λ. page 231
11.2.5: Noncrossing Condition 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
11.2.6: Extensions page 234
• 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
11.3: Definitions: Folding Motions of 1D Paper page 236
• Time Continuity of Order page 236
11.4: Definitions: Folded States of 2D Paper page 237
11.4.1: 2D Paper page 237
11.4.2: Free Folded States of 2D Paper page 238
• 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
11.4.3: Smoothness and Creases of 2D Paper page 239
11.4.4: Order page 240
11.4.4.1: Antisymmetry Condition page 240
11.4.4.2: Transitivity Condition page 240
11.4.4.3: Consistency Condition page 241
11.4.4.4: Noncrossing Condition page 241
11.5: Definitions: Folding Motions of 2D Paper page 242
• Time Continuity of Order page 242
• Figure 11.10: (a) The image of ft + ε applied to Bp. (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
11.6: Folding Motions Exist page 244
11.6.1: Rolling between Flat Folded States page 244
• 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
11.6.2: Unfurling onto the Target Folded State 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
Chapter 12: Simple Crease Patterns page 249
12.1: One-Dimensional Flat Foldings page 249
• 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 ci end but not the cj 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 (ci, ci + 1), highlighted in bold. page 255
12.2: Single-Vertex Crease Patterns page 256
12.2.1: Flat-Foldable Single-Vertex Crease Patterns page 256
• 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
12.2.2: Flat-Foldable Single-Vertex Mountain-Valley Patterns page 260
• 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
12.2.3: 3D Foldings of Single-Vertex Crease Patterns page 270
• 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
12.3: Continuous Single-Vertex Foldability page 272
• Figure 12.16: Flexing of a spherical quadrilateral composed of (90°, 90°, 45°, 45°) arcs. page 273
Chapter 13: General Crease Patterns page 275
13.1: Local Flat Foldability is Easy page 275
13.1.1: Generic Case page 275
13.1.2: General Case page 276
• 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
13.2: Global Flat Foldability is Hard page 278
13.2.1: All-Positive Not-All-Equal 3-Satisfiability page 278
13.2.2: Reduction Overview page 279
13.2.3: Wire page 279
• 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
13.2.4: Not-All-Equal Clause page 280
13.2.5: Splitting and Routing 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
13.2.6: Putting It Together 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
13.2.7: Overlap Order from Valid Mountain-Valley Assignment page 285
Chapter 14: Map Folding page 287
• 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
14.1: Simple Folds 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
14.1.1: Simple Folds in 1D page 289
• Figure 14.3: An all-layers fold of 1D paper. page 290
14.2: Rectangular Maps: Reduction to 1D page 290
• Figure 14.4: Folding a 2 × 4 map via a sequence of three all-layers simple folds. page 291
14.3: Hardness of Folding Orthogonal Polygons page 292
• Figure 14.5: Hardness reduction from partition problem. page 293
• Figure 14.6: Semi-folded staircase confined between y coordinates of P1 and P2. page 294
14.4: Open Problems page 295
• Open Problem 14.2: Orthogonal Creases page 295
• Open Problem 14.3: Pseudopolynomial-time Map Folding page 295
Chapter 15: Silhouettes and Gift Wrapping page 297
• 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
15.1: Strip Folding 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
15.2: Hamiltonian Triangulation page 299
• Figure 15.4: Covering a triangle Ti by zig-zagging parallel to the edge ei incident to the next triangle Ti + 1, choosing the initial direction so that we end at the vertex vi + 1 opposite the next edge ei + 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
15.3: Seam Placement 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
15.4: Efficient Foldings page 303
• Open Problem 15.2: Efficient Silhouettes and Wrapping page 303
15.4.1: Cube Wrapping page 304
• 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
15.4.2: Checkerboard Folding 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
Chapter 16: The Tree Method page 307
16.1: Origami Bases page 307
• Figure 16.1: Lang's Scorpion varileg, opus 379. page 308
16.2: Uniaxial Bases 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
16.3: Everything is Possible page 311
• 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
16.4: Active Paths page 312
16.5: Scale Optimization page 313
• 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 x1=x2 on the paths, or else the path (x1, x2) violates Lemma 16.4.1. (b) Crossing active paths violate Lemma 16.4.1 on the cross-path (v1, w2). 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
16.6: Convex Decomposition page 316
• 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
16.7: Overview of Folding page 318
• 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
16.8: Universal Molecule 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
Chapter 17: One Complete Straight Cut page 325
• 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
17.1: Straight-Skeleton Method page 327
• Figure 17.3: One fold aligns two graph edges. page 328
17.1.1: Straight Skeleton 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
17.1.2: Perpendiculars page 330
• Figure 17.7: The straight skeleton (thin solid) and all perpendiculars (dashed) for the turtle from Figure 17.5. page 331
17.1.3: Strange Behavior page 331
17.1.3.1: Spiraling page 331
• Figure 17.8: Mountain-valley pattern for the turtle crease pattern from Figure 17.7, slightly simplified. page 332
17.1.3.2: Density page 332
• Figure 17.9: A simple example of spiraling. [Based on [DDL00, Fig. 8].] page 333
17.1.4: Corridors 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
17.1.5: Folded State for Linear Corridors page 336
• Figure 17.14: Flattening the tree from Figure 17.13. page 337
17.1.6: Circular Corridors page 338
17.2: Disk-Packing Method page 338
17.2.1: Parallel Offset page 339
• 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
17.2.2: Disk Packing page 341
• Figure 17.17: Triangle and quadrangle molecules: (a) crease patterns; (b) folded states; (c) overhead views. page 342
17.2.3: Decomposition into Triangles and Quadrangles page 342
17.2.4: Molecules page 342
17.2.5: Gluing Molecules page 343
• Figure 17.18: (a) Square polygon; (b) Disk packing and ribbon expanding the polygon (now dashed) by ±ε. page 343
17.2.5.1: Molecule tree 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
17.2.5.2: Mountain-valley assignment page 345
17.2.5.3: Three Proof Parts page 345
• 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
17.2.5.4: Part 1a: Folding the inner molecule subtree 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
17.2.5.5: Part 1b: Sewing the cut edges between inner molecules page 349
17.2.5.6: Part 2: Attaching the ribbon page 349
17.2.5.7: Part 3: Outer molecules page 350
17.2.6: Sink-Folding Molecules page 350
• 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
17.2.7: Arbitrary Graphs page 351
• 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 = P1, z = P2). page 353
17.2.7.1: Disjoint Nonnested Polygons page 353
17.2.7.2: 2-Regular Graphs: Nontouching Polygons page 354
17.2.7.3: General Graphs page 354
• Figure 17.26: Schematic diagram of the flat folding for a polygon P containing two polygons P1 and P2: (a). (b) before and (c) after sink folding. The ribbon offsets ±ε around P, P1, and P2 are shown pink. Cf. Fig. 17.16. page 355
17.2.8: Summary page 356
Chapter 18: Flattening Polyhedra page 357
18.1: Connection to Part III: Models of Folding page 357
• Figure 18.1: Flattening a cereal box. page 357
• Open Problem 18.1: Continuous Flattening page 358
18.2: Connection to Fold-and-Cut Problem page 358
• Figure 18.2: Solving the 2D polygon-flattening problem via the 2D fold-and-cut problem. page 359
18.3: Solution via Disk Packing page 359
• Open Problem 18.2: Flattening Higher Genus page 360
18.4: Partial Solution via Straight Skeleton 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
Chapter 19: Geometric Constructibility page 365
19.1: Trisection page 365
• Figure 19.1: Abe's method for trisecting an angle using origami. page 365
19.2: Huzita's Axioms and Hatori's Addition page 366
• 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
19.2.1: Hatori's Seventh Axiom page 369
• Figure 19.6: Hatori's Axiom A7. page 369
19.3: Constructible Numbers page 369
• Figure 19.7: Messer's method for doubling a cube using origami. page 370
19.4: Folding Regular Polygons page 371
19.5: Generalizing the Axioms to Solve All Polynomials? page 371
• Figure 19.8: Simulating an arbitrary linkage with n bars by folding n rulers. page 372
Chapter 20: Rigid Origami and Curved Creases page 375
20.1: Folding Paper Bags page 375
• 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
20.2: Curved Surface Approximation page 377
• 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
20.3: David Huffman's Curved-Folds Origami page 378
• Beyond page 379
• Figure 20.5: Three David Huffman constructions. [Credits: E. Huffman & T. Grant; Permission, E. Huffman, 2005] page 380
Part III: Polyhedra page 381
Chapter 21: Introduction and Overview page 383
21.1: Overview page 383
• 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
21.2: Curvature page 386
21.2.1: Smooth Curves page 386
21.2.2: Smooth Surfaces 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
21.2.3: Polyhedral Surfaces: Angle Deficit page 389
21.3: Gauss-Bonnet Theorem page 389
Chapter 22: Edge Unfolding of Polyhedra page 391
22.1: Introduction page 391
22.1.1: Applications in Manufacturing page 391
• Figure 22.1: Lundström Design vinyl phone. [Lundström Design, by permission.] page 392
22.1.2: Problem Features 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
22.1.3: Spanning Trees 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
22.2: Evidence For Edge Unfoldings page 398
22.3: Evidence Against Edge Unfoldings page 399
• 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
22.3.1: Schlickenrieder's Thesis 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
22.4: Ununfoldable Polyhedra page 404
• 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
22.5: Special Classes of Edge-Unfoldable Polyhedra page 410
• Figure 22.21: A prism. page 410
• Figure 22.22: A prismoid. The base B is a regular octagon. page 410
22.5.1: Prismoids page 411
• 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
22.5.2: Domes page 414
• 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
22.5.3: Convex Unfoldings page 417
• 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
22.5.4: Orthogonal Polyhedra page 420
• Orthostacks page 420
• Figure 22.34: (a) A four-piece orthostack: S = E0 ∪ E1 ∪ E2 ∪ E3. (b) Refined orthostack, highlighting the band B3, and showing only the additional edges needed by the algorithm. page 421
• Figure 22.35: One unit of a generic orthostack unfolding. The Zi 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
22.5.5: Other Classes? page 423
• 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
22.6: Vertex-Unfoldings 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 vi and vi + 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
Chapter 23: Reconstruction of Polyhedra page 433
• 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
23.1: Cauchy's Rigidity Theorem page 435
• Figure 23.2: Two different polyhedra with the same facial structure. page 436
23.1.1: Proof of Cauchy's Theorem page 437
• 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 Sv 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
23.2: Flexible Polyhedra page 440
• Figure 23.6: Half of a regular octahedron, flexing. page 441
23.2.1: Bricard's Flexible Octahedra page 441
• Table 23.1: Coordinates of vertices in Figure 23.7. page 441
23.2.2: Connelly's Flexible Polyhedron 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
23.2.3: Steffen's Flexible Polyhedron page 443
• 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
23.2.4: The Bellows Conjecture page 444
23.3: Alexandrov's Theorem page 445
• Convex Polyhedral Metrics page 445
• Alexandrov Gluing page 445
• Relation to Cauchy Rigidity page 446
23.3.1: Uniqueness 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
23.3.2: Extension to Smooth Surfaces page 449
23.3.3: D-Forms page 449
• 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
23.4: Sabitov's Algorithm 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
Chapter 24: Shortest Paths and Geodesics page 457
24.1: Introduction page 457
24.1.1: Source Unfolding page 458
• 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 v1, v2, v3, v4, and v0=(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 Tx incident to v. page 463
24.2: Shortest Paths Algorithms page 463
24.2.1: The Continuous Dijkstra Approach 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
24.2.2: Chen & Han's Algorithm page 465
24.3: Star Unfolding page 466
• 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 v0. 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
24.3.1: Nonoverlap of the Star Unfolding page 470
24.3.2: Cut Locus is a Voronoi Diagram page 471
• 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
24.3.3: Core/Anticore page 475
24.4: Geodesics: Lyusternik-Schnirelmann page 476
• 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
24.4.0.1: Relation to Edge-Unfolding page 479
• 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
24.5: Curve Development page 480
24.5.1: Closed Convex Curves page 481
24.5.2: Slice Curves page 481
• 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 = (c0, c1, c2, c3); (b) its development B. (c) slice curve (c0, c1, c2, c3, c4); (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 ci of Γ = ∂Q. [Based on Fig. 4 of [O'R03], by permission, Elsevier.] page 484
• Figure 24.24: Violation of Theorem 24.5.1. q1=q2 is the first point of self-contact; the initial portion of B, up to q2, is highlighted. [Based on Fig. 3 of [O'R03], by permission, Elsevier.] page 485
24.5.3: Band Unfolding 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
Chapter 25: Folding Polygons to Polyhedra page 487
25.1: Folding Polygons: Preliminaries page 487
25.1.1: Not-foldable Polygons page 487
• Figure 25.1: A not-foldable polygon. page 488
25.1.2: Perimeter Halving page 488
• Figure 25.2: A perimeter-halving fold of a pentagon. The gluing mappings of vertices v1 and v3 are shown. page 489
• Figure 25.3: (a) x varies over (z, vi) on ∂P; (b) xvi is the shortest path between those vertices on 𝒫. page 490
• Open Problem 25.1: Folding Polygons to (Nonconvex) Polyhedra page 490
25.1.3: Random Polygons Do Not Fold 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 r1 produces a new reflex vertex r1; (c) Gluing several convex vertices into r1. page 492
25.2: Edge-to-Edge Gluings 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
25.2.1: Dynamic Programming Formulation 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 {vi, vj} creates two subproblems for every possible gluing {ei, ek}. page 495
25.2.2: Example page 496
• Figure 25.8: A polygon with two distinct edge-to-edge foldings (based on [She75, Fig. 2].) page 496
25.2.3: Five Edge-to-Edge Foldings of the Latin Cross page 498
• 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
25.3: Gluing Trees page 501
• Figure 25.11: (a) A polygon, with fold creases shown dashed; (b) A gluing tree TG 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
25.3.1: Rolling Belts page 503
• Figure 25.14: (a) An equilateral triangle creased in the interior of each edge; (b) The gluing tree. page 504
25.3.2: Gluing Tree Properties 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
25.3.3: Hirata Half-Lengths Theorem page 506
• Open Problem 25.2: Finite Number of Foldings page 506
25.4: Exponential Number of Gluing Trees 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
25.5: General Gluing Algorithm page 510
• Figure 25.20: Mouth angle μ and mouth interval M. page 511
• Figure 25.21: Interval M for v5 implies sliding of v4 on e2. page 511
• Open Problem 25.3: Polynomial-time Folding Decision Algorithm page 514
25.6: The Foldings of the Latin Cross page 514
25.6.1: The Eighty-Five Foldings page 514
25.6.2: Shape Reconstruction page 515
25.6.2.1: Tetrahedron page 515
• Figure 25.23: Foldings to P1, …, P6: cube, two quadrilaterals, three tetrahedra. page 516
• Figure 25.24: Foldings to P7, …, P12: four tetrahedra and two pentahedra. page 517
• Figure 25.25: Foldings to P13, …, P18: a pentahedron, four hexahedra, and an octahedron. page 518
• Figure 25.26: Foldings to P19, …, P23: octahedra. page 519
• Figure 25.27: Computing p3 for a tetrahedron, in this case P4 (Figure 25.33), the edge-to-edge tetrahedral folding of the Latin cross (Figure 25.9). page 520
25.6.2.2: Five-Vertex Polyhedra: Hexahedra page 521
25.6.2.3: Six-Vertex Polyhedra: Octahedra page 521
• 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 e1 and e2; (b) The joining of the two to form octahedron P23 of Figure 25.36. page 522
25.6.3: The Twenty-Three Shapes page 523
• Figure 25.30: The 23 polyhedra foldable from the Latin cross. page 523
25.6.4: No Rolling Belts 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. (P2 is the edge-to-edge quadrilateral of Figure 25.10.) page 524
• Figure 25.33: Latin cross tetrahedra. (P4 is the edge-to-edge tetrahedron of Figure 25.10.) page 525
• Figure 25.34: Latin cross pentahedra. P11 has six vertices and is composed of two triangles and three quadrilaterals. P12 and P13 have five vertices and one quadrilateral face. (P12 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. P18, P19, P20, and P21 have two vertices each of degrees 2, 3, and 4, and are composed of three stacked tetrahedra. P22 and P23 have all vertices of degree 4, and are combinatorially equivalent to a regular octahedron. (P23 is the edge-to-edge octahedron of Figure 25.10.) page 526
25.7: The Foldings of a Square to Convex Polyhedra page 526
25.7.1: Foldings of Convex Polygons page 527
• Figure 25.37: A hexagon (a) folds via an `I` gluing tree to a doubly-covered rectangle (b). page 528
25.7.2: Foldings of Regular Polygons 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
25.7.3: The Foldings of a Square 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
25.8: Reconstructing the 3D Shapes page 533
• 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
25.8.1: Consequences and Conjectures 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
25.8.2: The Foldings of an Equilateral Triangle page 536
25.8.3: The Space of Foldings of a Convex Polygon 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
25.8.4: Dissection-Related Open Problems page 541
• 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
25.9: Enumerations of Foldings page 545
• Figure 25.54: (a) Ω(n2) 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
25.10: Enumerations of Cuttings page 548
• Figure 25.56: (a) Geometric cut tree 𝒯C on the surface of a cube; (b) The corresponding combinatorial cut tree TC. page 549
• Figure 25.57: (a) Doubly covered rectangle with cut path; x is the midpoint of edge v1v4. (b) Unfolding. (c–d): Another cut path and its unfolding. page 550
• Figure 25.58: (a) Polyhedron Q; (b) Unfolding via (red) cut tree T1001101. page 551
• Figure 25.59: (a) Polyhedron Q, with a cut tree labled T⋯0022020100. (b) Unfolding to polygon P. page 552
25.11: Orthogonal Polyhedra page 553
25.11.1: Orthogonal Nets page 553
• 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
25.11.2: NonOrthogonal Polyhedra page 555
• 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
25.11.3: “Rigid Nets” 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
Chapter 26: Higher Dimensions page 559
26.1: Part I page 559
• Figure 26.1: Extruding a linkage into an equivalent collection of polygons (rectangles) hinged together at their edges. page 559
26.2: Part II page 560
• Open Problem 26.1: Higher-Dimensional Fold-and-Cut page 560
• Open Problem 26.2: Flattening Complexes page 561
26.3: Part III page 561
26.3.1: Tesseract 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
26.3.2: 3-Manifolds Built of Boxes page 561
• Figure 26.3: “Corpus Hypercubus”. Salvador Dali, 1955. ©2006 Salvador Dali, Gala-Salvador Dali Foundation / Artists Rights Society, New York. page 562
26.3.3: Vertex Unfolding page 563
26.3.4: Source Unfolding and Star Unfolding page 563
• Open Problem 26.3: Ridge Unfolding page 564
Bibliography page 565