Geometric Folding Algorithms:
Linkages, Origami, and Polyhedra

Erik D. Demaine and Joseph O'Rourke

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
0.1.2: II: Origami Design page 12
0.1.3: III: Unfolding to Net page 13
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
Part I: Linkages page 19
Chapter 1: Problem Classification and Examples page 21
1.1: Classification page 22
1.2: Applications page 24
1.2.1: Robotics page 24
1.2.2: Mechanisms page 25
1.2.3: Bending Machines page 27
1.2.4: Protein Folding page 28
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
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
2.2.2: Three Constructions Sketched page 38
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
3.1.3: Peaucellier Linkage page 46
3.2: Kempe's Universality Theorem page 48
3.2.1: Kempe's Proof page 48
3.2.2: The Flaw and Repairs page 54
3.2.2.1: Bracing the Parallelogram page 54
3.2.2.2: Bracing the Contraparallelogram page 56
3.2.3: Recap page 58
3.3: Hart's Inversor page 59
Chapter 4: Rigid Frameworks page 63
4.1: Brief History page 63
4.2: Rigidity page 63
4.3: Generic Rigidity page 64
4.3.1: Laman's Theorem page 65
4.3.2: Higher Dimensions page 68
4.3.3: Henneberg Constructions page 69
4.3.4: Global Rigidity page 70
4.4: Infinitesimal Rigidity page 71
4.4.1: Infinitesimal Length Constraint page 71
4.4.2: Rigidity Matrix page 72
4.4.3: Connection between Rigidity and Infinitesimal Rigidity page 74
4.5: Tensegrities 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
4.5.5: Linkages and Tensegrities page 80
4.6: Polyhedral Liftings page 81
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
5.1.1.2: Annulus page 84
5.1.1.3: Two-Kinks Theorem page 87
5.1.1.4: Solving a 3-link problem page 88
5.1.2: Turning a Polygon Inside-Out page 88
5.2: Reconfiguration in Confined Regions page 93
5.2.1: Chains Confined to Circles page 93
5.2.2: Chains Confined to Squares page 95
5.2.3: Chains Confined to Equilateral Triangles page 95
5.3: Reconfiguration without Self-Crossing page 96
5.3.1: 2D: Convex Polygons page 98
5.3.2: 2D/3D: Arbitrary Polygons page 101
5.3.2.1: Pocket Flipping page 102
5.3.2.2: Deflations page 107
5.3.2.3: Variations on Flipping page 109
5.3.2.4: Arch Algorithms page 111
5.3.3: 3D: Simple Projection page 114
Chapter 6: Locked Chains page 117
6.1: Introduction page 117
6.2: History page 119
6.3: Locked Chains in 3D page 120
6.3.1: Locked Open Chains page 120
6.3.2: Locked Closed Chains page 122
6.3.3: Chains of Fat Links page 123
6.4: No Locked Chains in 4D page 124
6.5: Locked Trees in 2D page 126
6.6: No Locked Chains in 2D page 129
6.6.1: Expansiveness and the Connection to Tensegrities page 132
6.6.2: Combinatorial Argument page 133
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
6.7.2: Unlocking 2D Chains using Pseudotriangulations page 141
6.7.3: Unlocking 2D Chains using Energy page 146
6.8: Infinitesimally Locked Linkages in 2D page 148
6.8.1: Stronger Definitions of Locked page 150
6.8.2: Self-Touching Configurations page 152
6.8.3: Connection to Rigidity page 152
6.8.4: Proving Trees Locked page 153
6.8.5: Other Problems on Self-Touching Linkages page 156
6.9: 3D Polygons with a Simple Projection page 156
Chapter 7: Interlocked Chains page 161
7.1: 2-chains page 163
7.2: 3-chains page 164
7.3: 4-chains page 166
Chapter 8: Joint-Constrained Motion page 171
8.1: Fixed-Angle Linkages page 171
8.1.1: Extreme Spans page 173
8.1.2: Flattening page 176
8.1.3: Flat-State Connectivity page 177
8.1.4: Flat-State Disconnected Linkages page 180
8.1.5: Partially Rigid Orthogonal Tree page 180
8.1.6: Orthogonal Graph page 182
8.1.7: Open Orthogonal Chains page 184
8.2: Convex Chains page 186
8.2.1: Cauchy's Arm Lemma page 186
8.2.2: Uses and Generalizations of Cauchy's Lemma page 188
8.2.3: Straightening Convex Chains page 189
Chapter 9: Protein Folding page 193
9.1: Producible Polygonal Protein Chains page 193
9.1.1: Notation page 194
9.1.2: Chain Production page 196
9.1.3: Main Results page 197
9.1.4: Producible ≡ Flattenable page 197
9.1.5: Random Chains page 200
9.1.6: Open Problems on Unit Chains page 201
9.2: Probabilistic Roadmaps page 202
9.3: HP Model page 206
9.3.1: NP-completeness page 207
9.3.2: Approximation Algorithms page 209
9.3.3: Unique optimal Foldings page 210
Part II: Paper page 215
Chapter 10: Introduction page 217
10.2: History of Origami Mathematics page 219
10.3: Terminology page 219
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
11.1.3: Smoothness and Creases of One-Dimensional Paper page 226
11.2: Definitions: Folded States of 1D Paper page 227
11.2.1: Order page 227
11.2.2: Antisymmetry Condition page 229
11.2.3: Transitivity Condition page 230
11.2.4: Consistency Condition page 230
11.2.5: Noncrossing Condition page 231
11.2.6: Extensions page 234
11.3: Definitions: Folding Motions of 1D Paper 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
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
11.6: Folding Motions Exist page 244
11.6.1: Rolling between Flat Folded States page 244
11.6.2: Unfurling onto the Target Folded State page 246
Chapter 12: Simple Crease Patterns page 249
12.1: One-Dimensional Flat Foldings page 249
12.2: Single-Vertex Crease Patterns page 256
12.2.1: Flat-Foldable Single-Vertex Crease Patterns page 256
12.2.2: Flat-Foldable Single-Vertex Mountain-Valley Patterns page 260
12.2.3: 3D Foldings of Single-Vertex Crease Patterns page 270
12.3: Continuous Single-Vertex Foldability page 272
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
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
13.2.4: Not-All-Equal Clause page 280
13.2.5: Splitting and Routing page 280
13.2.6: Putting It Together page 282
13.2.7: Overlap Order from Valid Mountain-Valley Assignment page 285
Chapter 14: Map Folding page 287
14.1: Simple Folds page 288
14.1.1: Simple Folds in 1D page 289
14.2: Rectangular Maps: Reduction to 1D page 290
14.3: Hardness of Folding Orthogonal Polygons page 292
14.4: Open Problems page 295
Chapter 15: Silhouettes and Gift Wrapping page 297
15.1: Strip Folding page 298
15.2: Hamiltonian Triangulation page 299
15.3: Seam Placement page 301
15.4: Efficient Foldings page 303
15.4.1: Cube Wrapping page 304
15.4.2: Checkerboard Folding page 304
Chapter 16: The Tree Method page 307
16.1: Origami Bases page 307
16.2: Uniaxial Bases page 308
16.3: Everything is Possible page 311
16.4: Active Paths page 312
16.5: Scale Optimization page 313
16.6: Convex Decomposition page 316
16.7: Overview of Folding page 318
16.8: Universal Molecule page 319
Chapter 17: One Complete Straight Cut page 325
17.1: Straight-Skeleton Method page 327
17.1.1: Straight Skeleton page 328
17.1.2: Perpendiculars page 330
17.1.3: Strange Behavior page 331
17.1.3.1: Spiraling page 331
17.1.3.2: Density page 332
17.1.4: Corridors page 333
17.1.5: Folded State for Linear Corridors page 336
17.1.6: Circular Corridors page 338
17.2: Disk-Packing Method page 338
17.2.1: Parallel Offset page 339
17.2.2: Disk Packing page 341
17.2.3: Decomposition into Triangles and Quadrangles page 342
17.2.4: Molecules page 342
17.2.5: Gluing Molecules page 343
17.2.5.1: Molecule tree page 343
17.2.5.2: Mountain-valley assignment page 345
17.2.5.3: Three Proof Parts page 345
17.2.5.4: Part 1a: Folding the inner molecule subtree page 346
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
17.2.7: Arbitrary Graphs page 351
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
17.2.8: Summary page 356
Chapter 18: Flattening Polyhedra page 357
18.1: Connection to Part III: Models of Folding page 357
18.2: Connection to Fold-and-Cut Problem page 358
18.3: Solution via Disk Packing page 359
18.4: Partial Solution via Straight Skeleton page 360
Chapter 19: Geometric Constructibility page 365
19.1: Trisection page 365
19.2: Huzita's Axioms and Hatori's Addition page 366
19.2.1: Hatori's Seventh Axiom page 369
19.3: Constructible Numbers page 369
19.4: Folding Regular Polygons page 371
19.5: Generalizing the Axioms to Solve All Polynomials? page 371
Chapter 20: Rigid Origami and Curved Creases page 375
20.1: Folding Paper Bags page 375
20.2: Curved Surface Approximation page 377
20.3: David Huffman's Curved-Folds Origami page 378
Part III: Polyhedra page 381
Chapter 21: Introduction and Overview page 383
21.1: Overview page 383
21.2: Curvature page 386
21.2.1: Smooth Curves page 386
21.2.2: Smooth Surfaces page 386
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
22.1.2: Problem Features page 392
22.1.3: Spanning Trees page 396
22.2: Evidence For Edge Unfoldings page 398
22.3: Evidence Against Edge Unfoldings page 399
22.3.1: Schlickenrieder's Thesis page 402
22.4: Ununfoldable Polyhedra page 404
22.5: Special Classes of Edge-Unfoldable Polyhedra page 410
22.5.1: Prismoids page 411
22.5.2: Domes page 414
22.5.3: Convex Unfoldings page 417
22.5.4: Orthogonal Polyhedra page 420
22.5.5: Other Classes? page 423
22.6: Vertex-Unfoldings page 424
Chapter 23: Reconstruction of Polyhedra page 433
23.1: Cauchy's Rigidity Theorem page 435
23.1.1: Proof of Cauchy's Theorem page 437
23.2: Flexible Polyhedra page 440
23.2.1: Bricard's Flexible Octahedra page 441
23.2.2: Connelly's Flexible Polyhedron page 441
23.2.3: Steffen's Flexible Polyhedron page 443
23.2.4: The Bellows Conjecture page 444
23.3: Alexandrov's Theorem page 445
23.3.1: Uniqueness page 446
23.3.2: Extension to Smooth Surfaces page 449
23.3.3: D-Forms page 449
23.4: Sabitov's Algorithm page 451
Chapter 24: Shortest Paths and Geodesics page 457
24.1: Introduction page 457
24.1.1: Source Unfolding page 458
24.2: Shortest Paths Algorithms page 463
24.2.1: The Continuous Dijkstra Approach page 463
24.2.2: Chen & Han's Algorithm page 465
24.3: Star Unfolding page 466
24.3.1: Nonoverlap of the Star Unfolding page 470
24.3.2: Cut Locus is a Voronoi Diagram page 471
24.3.3: Core/Anticore page 475
24.4: Geodesics: Lyusternik-Schnirelmann page 476
24.4.0.1: Relation to Edge-Unfolding page 479
24.5: Curve Development page 480
24.5.1: Closed Convex Curves page 481
24.5.2: Slice Curves page 481
24.5.3: Band Unfolding page 485
Chapter 25: Folding Polygons to Polyhedra page 487
25.1: Folding Polygons: Preliminaries page 487
25.1.1: Not-foldable Polygons page 487
25.1.2: Perimeter Halving page 488
25.1.3: Random Polygons Do Not Fold page 490
25.2: Edge-to-Edge Gluings page 492
25.2.1: Dynamic Programming Formulation page 493
25.2.2: Example page 496
25.2.3: Five Edge-to-Edge Foldings of the Latin Cross page 498
25.3: Gluing Trees page 501
25.3.1: Rolling Belts page 503
25.3.2: Gluing Tree Properties page 504
25.3.3: Hirata Half-Lengths Theorem page 506
25.4: Exponential Number of Gluing Trees page 506
25.5: General Gluing Algorithm page 510
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
25.6.2.2: Five-Vertex Polyhedra: Hexahedra page 521
25.6.2.3: Six-Vertex Polyhedra: Octahedra page 521
25.6.3: The Twenty-Three Shapes page 523
25.6.4: No Rolling Belts page 523
25.7: The Foldings of a Square to Convex Polyhedra page 526
25.7.1: Foldings of Convex Polygons page 527
25.7.2: Foldings of Regular Polygons page 528
25.7.3: The Foldings of a Square page 530
25.8: Reconstructing the 3D Shapes page 533
25.8.1: Consequences and Conjectures page 535
25.8.2: The Foldings of an Equilateral Triangle page 536
25.8.3: The Space of Foldings of a Convex Polygon page 536
25.8.4: Dissection-Related Open Problems page 541
25.9: Enumerations of Foldings page 545
25.10: Enumerations of Cuttings page 548
25.11: Orthogonal Polyhedra page 553
25.11.1: Orthogonal Nets page 553
25.11.2: NonOrthogonal Polyhedra page 555
25.11.3: “Rigid Nets” page 556
Chapter 26: Higher Dimensions page 559
26.1: Part I page 559
26.2: Part II page 560
26.3: Part III page 561
26.3.1: Tesseract page 561
26.3.2: 3-Manifolds Built of Boxes page 561
26.3.3: Vertex Unfolding page 563
26.3.4: Source Unfolding and Star Unfolding page 563
Bibliography page 565