Table of Contents
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 sixaxis 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 socalled “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 nonselfintersecting. 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 x_{1}+x_{3}+x_{4}=x_{2}+x_{5}+x_{6}. page 41
 Figure 2.6: (a) Initial configuration. The dashed segment starting from v_{0} represents a large collection of unit links. The slashes indicate interruptions. Note the tunnel is only 2 + ε units high. (b) Intermediate configuration, when R_{100} 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: Straightline 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 figure8 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 e_{1}+e_{2}+e_{3} is independent of the order of the terms. page 86
 Figure 5.4: Inner radius r_{i}=ℓ_{M}−s. page 86
5.1.1.3: TwoKinks 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 3link problem page 88
5.1.2: Turning a Polygon InsideOut 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 linetracking motion. The initial position of the chain is shown with solid lines, with v_{2} tracking line L to positions v′_{2} and v”_{2}. This is not a simple linetracking motion because the angle at v_{3} 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 2^{n/3} disconnected configurations. page 93
 Figure 5.12: (a) The five links have orientations LLRRL; (b) orientations RLLLR. Thus all but L_{2} 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 L_{1}=(v_{0}, v_{1}) 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 SelfCrossing page 96
 Figure 5.16: “Stuck” chains: (a) x_{1} > 0.483; (b) x_{2}=0.5; (c) x_{3} > 0.866. page 97
 Figure 5.17: (a) Left and Right in neighborhood of a vertex; (b) C = (v_{0}, …, v_{8}) does not selfcross, for it stays on the same side of v_{0}v_{1} both in a neighborhood of v_{3}, and in neighborhoods of v_{6} and v_{7}. But if v_{8} is replaced by v′_{8}, then C′ = (v_{0}, …, v′_{8}) does selfcross. page 97
 Box 5.1: SelfCrossing 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 (v_{i}, v_{j}, v_{k}, v_{l}). 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 PocketFlip 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^{0} ⊆ C^{0} ⊈ P^{1}. page 106
 Box 5.2: Proof Pitfalls page 107
5.3.2.2: Deflations page 107
 Figure 5.27: (a) Original polygon P_{0}, with lengths 3 + 6 = 4 + 5; (b) deflation step; (c) P_{1}; (d) deflation step; (e) P_{2}; (f) deflation step. page 108
 Figure 5.28: An attempted deflation produces a selfcrossing polygon. page 109
5.3.2.3: Variations on Flipping page 109
 Figure 5.29: A polygon P such that every pop produces a selfcrossing. 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: v_{i + 1} rotates up the circle C until it hits Π_{ε}. page 111
 Figure 5.31: (a) The arch in Π_{z} after the ith 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_{i}v_{i − 1}v_{j + 1}v_{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
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: e_{0} 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 (v_{1}, v_{2}, v_{3}, v_{4}). A reconfiguration of v_{1} to v′_{1} and v_{0} to v′_{0} illustrates that v_{1} remains interior and v_{0} remains exterior to B. page 121
6.3.2: Locked Closed Chains page 122
 Figure 6.4: K^{2} (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 5Chain 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 “offscreen.” (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
 MaxwellCremona 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 singledegreeoffreedom 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 singledegreeoffreedom 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 29link closed chain via gradient descent of energy. [From [CDIO04].] page 147
 Figure 6.21: Convexifying a 380link 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: Selftouching 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: SelfTouching Configurations page 152
6.8.3: Connection to Rigidity page 152
6.8.4: Proving Trees Locked page 153
 Step 1: Model as selftouching configuration page 153
 Figure 6.24: (a) Locked tree. (b) Selftouching version. (c) One petal and adjacent pieces. Short light edges denote zerolength sliding struts. BlowUps 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 degree3 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 SelfTouching Linkages page 156
 Open Problem 6.5: Selftouching 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) c′d 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 kchain; △ = closed (rigid) 3chain; □ = closed, flexible 4chain; pentagon = closed, flexible 5chain. page 163
7.1: 2chains page 163
 Figure 7.2: Three 2chains (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 2chain page 164
7.2: 3chains page 164
 Figure 7.3: Nonuniform scaling keeps the middle links parallel to the xyplane. (Scaled versions of the end links are not shown.) page 165
 Figure 7.4: A quadrilateral and a 3chain can lock. [Fig. 6 in [DLOS03], by permission, Elsevier.] page 166
7.3: 4chains page 166
 Figure 7.5: A triangle and a 4chain can lock. [Fig. 2 in [DLOS03], by permission, Elsevier.] page 167
 Figure 7.6: The first few twocomponent links. Images produced by
knotplot
: http://www.knotplot.com/. page 167
 Box 7.1: Topological Links page 167
 Figure 7.7: When v_{0} touches B, point v_{1} must be exterior to B′ by at least R, and therefore v_{2} and v_{3} 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_{0} or v_{4} touch the boundary of B. [Fig. 4 in [DLOS03], by permission, Elsevier.] page 169
 Figure 7.9: The link 4^{2}_{1}, formed when links e_{1} and e_{4} both pierce △abc. [Fig. 5 in [DLOS03], by permission, Elsevier.] page 169
 Figure 7.10: Interlocked open, flexible 3 and 4chains. [Fig. 6 from [DLOS02], by permission, Elsevier.] page 169
Chapter 8: JointConstrained Motion page 171
8.1: FixedAngle 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 e′_{1} and e′_{4} 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 fixedangle 4chain cannot be flattened, although if all joints are flexible it is not locked. Light colored circles constrain positions of v_{0} and v_{4}. page 176
 Flattening NPHard page 177
 Figure 8.8: The “key” e_{n} fits in the “lock” if and only if S has a partition. page 177
8.1.3: FlatState Connectivity page 177
 Figure 8.9: (a) and (b) Flat embeddings of the lock chain; (c) and (d) selfcrossing 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: Flatstate Connectivity of Open Chains page 179
8.1.4: FlatState 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 cbranches collide when rotated above. Here the linkage is drawn with aa_{1} = cc_{1} and bb_{1} = dd_{1}. page 181
 Figure 8.12: The a and bbranches 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 achain is not linked with the bchain in (a), but is linked in (b). page 183
 Figure 8.14: An orthogonal graph linkage that is flatstate disconnected. page 183
 Open Problem 8.3: Flatstate Connectivity of Orthogonal Trees page 184
8.1.7: Open Orthogonal Chains page 184
 Figure 8.15: (a) Lifting edges e_{1}=(v_{0}, v_{1}) and e_{2}=(v_{1}, v_{2}): a, b, c. (b) Lifting edges e_{3} and e_{4}: 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 (v_{0} is not on the hull); (b) v′_{0}−v′_{n} < v_{0}−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 xaxis; (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 b_{i + 1} on the cone have the same turn angle at b_{i}. page 191
Chapter 9: Protein Folding page 193
9.1: Producible Polygonal Protein Chains page 193
 Figure 9.1: The ribosome R in crosssection. 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 xyplane. [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 e_{0} and e_{1} during t ∈ [t_{0}, t_{1}]. [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, fixedangle, 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 Fixedangle 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 8dof 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 fourframe 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: NPcompleteness 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 OneDimensional Paper page 224
11.1.2: Free Folding Motions of OneDimensional Paper page 225
 Time Continuity of Geometry page 226
11.1.3: Smoothness and Creases of OneDimensional 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 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
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: OneDimensional 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 mountainvalley 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 mountainvalley pattern that when crimped is no longer mingling. page 254
 Figure 12.7: Moving layers of paper out of the zigzag formed by a crimp (c_{i}, c_{i + 1}), highlighted in bold. page 255
12.2: SingleVertex Crease Patterns page 256
12.2.1: FlatFoldable SingleVertex Crease Patterns page 256
 Figure 12.8: Flat foldings of singlevertex 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 mountainvalley assignment for a flatfoldable singlevertex 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: FlatFoldable SingleVertex MountainValley 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 selfintersect, 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 SingleVertex 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 selfintersections in the attempted folded state. page 272
 Open Problem 12.1: 3D SingleVertex Fold page 272
12.3: Continuous SingleVertex 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: AllPositive NotAllEqual 3Satisfiability 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: NotAllEqual Clause page 280
13.2.5: Splitting and Routing page 280
 Figure 13.4: NotAllEqual clause gadget: the crease pattern, the local equal/opposite pairing, all valid mountainvalley assignments up to rotational symmetry, an invalid mountainvalley 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 mountainvalley 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 mountainvalley assignments, and two invalid mountainvalley assignments. page 283
 Figure 13.7: Overview of the reduction from AllPositive NotAllEqual 3Satisfiability to flat foldability of a crease pattern. page 284
13.2.7: Overlap Order from Valid MountainValley Assignment page 285
Chapter 14: Map Folding page 287
 Open Problem 14.1: Map Folding page 287
 Figure 14.1: (a) A mapfolding 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 somelayers simple folds, but not by one or alllayers simple folds. (b) Top view of a flat folding. page 289
14.1.1: Simple Folds in 1D page 289
 Figure 14.3: An alllayers 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 alllayers 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: Semifolded staircase confined between y coordinates of P_{1} and P_{2}. page 294
14.4: Open Problems page 295
 Open Problem 14.2: Orthogonal Creases page 295
 Open Problem 14.3: Pseudopolynomialtime Map Folding page 295
Chapter 15: Silhouettes and Gift Wrapping page 297
 Figure 15.1: (a) Polygonal silhouette of a horse. (b) Polygonal twocolor 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: Colorreversal gadget. page 299
15.2: Hamiltonian Triangulation page 299
 Figure 15.4: Covering a triangle T_{i} by zigzagging 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 zigzags. 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 colorreversal perimeter. page 305
 Figure 15.10: Shortest possible Eulerian tours that visit all colorreversal 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 colorreversal 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 xyplane, 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 x_{1}=x_{2} on the paths, or else the path (x_{1}, x_{2}) violates Lemma 16.4.1. (b) Crossing active paths violate Lemma 16.4.1 on the crosspath (v_{1}, w_{2}). 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 fivepointed 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: StraightSkeleton 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 degree0 or degree1 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: Mountainvalley 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 3coloring 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: DiskPacking 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: Mountainvalley assignment page 345
17.2.5.3: Three Proof Parts page 345
 Figure 17.20: (a) A 7arm 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 sideview 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: SinkFolding Molecules page 350
 Figure 17.23: Sinkfolding 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 regionboundary tree. page 352
 Figure 17.25: Regionboundary 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_{1}, z = P_{2}). page 353
17.2.7.1: Disjoint Nonnested Polygons page 353
17.2.7.2: 2Regular 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 P_{1} and P_{2}: (a). (b) before and (c) after sink folding. The ribbon offsets ±ε around P, P_{1}, and P_{2} 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 FoldandCut Problem page 358
 Figure 18.2: Solving the 2D polygonflattening problem via the 2D foldandcut 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 polygonflattening from perpendiculars in the 2D foldandcut 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 CurvedFolds 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: EdgeUnfolding 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: GaussBonnet 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: rightmostascendingedgeunfold, Figure 40c in [Sch97]. page 403
 Figure 22.12: normalorderunfold Figure 42b in [Sch97]. Overlap circled. page 403
22.4: Ununfoldable Polyhedra page 404
 Figure 22.13: steepestedgeunfold: Figure 35 in [Sch97]. page 405
 Figure 22.14: flatspanningtreeunfold Figure 38 in [Sch97]. page 405
 Figure 22.15: An open triangulated hat that cannot be edgeunfolded. 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 EdgeUnfoldable 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 nonstrictlyconvex 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 fourpiece orthostack: S = E_{0} ∪ E_{1} ∪ E_{2} ∪ E_{3}. (b) Refined orthostack, highlighting the band B_{3}, 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: EdgeUnfolding Polyhedra Built From Cubes page 422
22.5.5: Other Classes? page 423
 Open Problem 22.5: EdgeUnfolding for Nonacute Faces page 423
 Open Problem 22.6: EdgeUnfolding for Nonobtuse 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: 1to4 refinement. page 424
22.6: VertexUnfoldings 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) 16face 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: Vertexunfolding 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 areaweighted 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 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
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, dashdots 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: DForms page 449
 Figure 23.12: Based on Figure 6.49 in [PW01, p. 401], by permission. page 450
 Figure 23.13: Dform (b) constructed from two “racetracks” (a). page 450
 Figure 23.14: A pitaform. page 450
 Open Problem 23.1: Dforms and PitaForms 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 “backview” (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_{1}, v_{2}, v_{3}, v_{4}, and v_{0}=(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
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 v_{0}. 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: LyusternikSchnirelmann 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 LyusternikSchnirelmann 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 EdgeUnfolding 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 EdgeUnfolding 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 = (c_{0}, c_{1}, c_{2}, c_{3}); (b) its development B. (c) slice curve (c_{0}, c_{1}, c_{2}, c_{3}, c_{4}); (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_{1}=q_{2} is the first point of selfcontact; the initial portion of B, up to q_{2}, 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 edgeunfolding 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: Notfoldable Polygons page 487
 Figure 25.1: A notfoldable polygon. page 488
25.1.2: Perimeter Halving page 488
 Figure 25.2: A perimeterhalving fold of a pentagon. The gluing mappings of vertices v_{1} and v_{3} 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
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 r_{1} produces a new reflex vertex r′_{1}; (c) Gluing several convex vertices into r_{1}. page 492
25.2: EdgetoEdge Gluings page 492
 Figure 25.5: An unfolding of a randomlygenerated 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 {v_{i}, v_{j}} creates two subproblems for every possible gluing {e_{i}, e_{k}}. page 495
25.2.2: Example page 496
 Figure 25.8: A polygon with two distinct edgetoedge foldings (based on [She75, Fig. 2].) page 496
25.2.3: Five EdgetoEdge Foldings of the Latin Cross page 498
 Figure 25.9: The five edgetoedge 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 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
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 foldpoint 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 HalfLengths 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 4star. 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 v_{5} implies sliding of v_{4} on e_{2}. page 511
 Open Problem 25.3: Polynomialtime Folding Decision Algorithm page 514
25.6: The Foldings of the Latin Cross page 514
25.6.1: The EightyFive Foldings page 514
25.6.2: Shape Reconstruction page 515
25.6.2.1: Tetrahedron page 515
 Figure 25.23: Foldings to P_{1}, …, P_{6}: cube, two quadrilaterals, three tetrahedra. page 516
 Figure 25.24: Foldings to P_{7}, …, P_{12}: four tetrahedra and two pentahedra. page 517
 Figure 25.25: Foldings to P_{13}, …, P_{18}: a pentahedron, four hexahedra, and an octahedron. page 518
 Figure 25.26: Foldings to P_{19}, …, P_{23}: octahedra. page 519
 Figure 25.27: Computing p_{3} for a tetrahedron, in this case P_{4} (Figure 25.33), the edgetoedge tetrahedral folding of the Latin cross (Figure 25.9). page 520
25.6.2.2: FiveVertex Polyhedra: Hexahedra page 521
25.6.2.3: SixVertex 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 e_{1} and e_{2}; (b) The joining of the two to form octahedron P_{23} of Figure 25.36. page 522
25.6.3: The TwentyThree 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. (P_{2} is the edgetoedge quadrilateral of Figure 25.10.) page 524
 Figure 25.33: Latin cross tetrahedra. (P_{4} is the edgetoedge tetrahedron of Figure 25.10.) page 525
 Figure 25.34: Latin cross pentahedra. P_{11} has six vertices and is composed of two triangles and three quadrilaterals. P_{12} and P_{13} have five vertices and one quadrilateral face. (P_{12} is the edgetoedge 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_{18}, P_{19}, P_{20}, and P_{21} have two vertices each of degrees 2, 3, and 4, and are composed of three stacked tetrahedra. P_{22} and P_{23} have all vertices of degree 4, and are combinatorially equivalent to a regular octahedron. (P_{23} is the edgetoedge 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 doublycovered rectangle (b). page 528
25.7.2: Foldings of Regular Polygons page 528
 Figure 25.38: (a,b) Flat foldings of an ngon, n even (n = 8). (c) Flat folding of an ngon, n odd (n = 7). page 529
 Figure 25.39: Duodecagon, n = 12, x and y are perimeterhalving 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: DissectionRelated 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) Ω(n^{2}) combinatorial types achieved by rolling the perimeter belt; (b) Only O(n) possible disjoint vvpairings. page 546
 Figure 25.55: (a) Polygon P; (b) One four foldpoint 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 T_{C}. page 549
 Figure 25.57: (a) Doubly covered rectangle with cut path; x is the midpoint of edge v_{1}v_{4}. (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
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: HigherDimensional FoldandCut 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: 3Manifolds Built of Boxes page 561
 Figure 26.3: “Corpus Hypercubus”. Salvador Dali, 1955. ©2006 Salvador Dali, GalaSalvador 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