You are previewing Geometric Folding Algorithms.
O'Reilly logo
Geometric Folding Algorithms

Book Description

Did you know that any straight-line drawing on paper can be folded so that the complete drawing can be cut out with one straight scissors cut? That there is a planar linkage that can trace out any algebraic curve, or even 'sign your name'? Or that a 'Latin cross' unfolding of a cube can be refolded to 23 different convex polyhedra? Over the past decade, there has been a surge of interest in such problems, with applications ranging from robotics to protein folding. With an emphasis on algorithmic or computational aspects, this treatment gives hundreds of results and over 60 unsolved 'open problems' to inspire further research. The authors cover one-dimensional (1D) objects (linkages), 2D objects (paper), and 3D objects (polyhedra). Aimed at advanced undergraduate and graduate students in mathematics or computer science, this lavishly illustrated book will fascinate a broad audience, from school students to researchers.

Table of Contents

  1. Cover
  2. Half Title
  3. Title Page
  4. Copyright
  5. Dedication
  6. Contents
  7. Preface
  8. 0. Introduction
    1. 0.1 Design Problems
    2. 0.2 Foldability Questions
  9. Part I: Linkages
    1. 1. Problem Classification and Examples
      1. 1.1 Classification
      2. 1.2 Applications
    2. 2. Upper and Lower Bounds
      1. 2.1 General Algorithms and Upper Bounds
      2. 2.2 Lower Bounds
    3. 3. Planar Linkage Mechanisms
      1. 3.1 Straight-Line Linkages
      2. 3.2 Kempe’s Universality Theorem
      3. 3.3 Hart’s Inversor
    4. 4. Rigid Frameworks
      1. 4.1 Brief History
      2. 4.2 Rigidity
      3. 4.3 Generic Rigidity
      4. 4.4 Infinitesimal Rigidity
      5. 4.5 Tensegrities
      6. 4.6 Polyhedral Liftings
    5. 5. Reconfiguration of Chains
      1. 5.1 Reconfiguration Permitting Intersection
      2. 5.2 Reconfiguration in Confined Regions
      3. 5.3 Reconfiguration Without Self-Crossing
    6. 6. Locked Chains
      1. 6.1 Introduction
      2. 6.2 History
      3. 6.3 Locked Chains in 3D
      4. 6.4 No Locked Chains in 4D
      5. 6.5 Locked Trees in 2D
      6. 6.6 No Locked Chains in 2D
      7. 6.7 Algorithms for Unlocking 2D Chains
      8. 6.8 Infinitesimally Locked Linkages in 2D
      9. 6.9 3D Polygons with a Simple Projection
    7. 7. Interlocked Chains
      1. 7.1 2-Chains
      2. 7.2 3-Chains
      3. 7.3 4-Chains
    8. 8. Joint-Constrained Motion
      1. 8.1 Fixed-Angle Linkages
      2. 8.2 Convex Chains
    9. 9. Protein Folding
      1. 9.1 Producible Polygonal Protein Chains
      2. 9.2 Probabilistic Roadmaps
      3. 9.3 HP Model
  10. Part II: Origami
    1. 10. Introduction
      1. 10.1 History of Origami
      2. 10.2 History of Origami Mathematics
      3. 10.3 Terminology
      4. 10.4 Overview
    2. 11. Foundations
      1. 11.1 Definitions: Getting Started
      2. 11.2 Definitions: Folded States of 1D Paper
      3. 11.3 Definitions: Folding Motions of 1D Paper
      4. 11.4 Definitions: Folded States of 2D Paper
      5. 11.5 Definitions: Folding Motions of 2D Paper
      6. 11.6 Folding Motions Exist
    3. 12. Simple Crease Patterns
      1. 12.1 One-Dimensional Flat Foldings
      2. 12.2 Single-Vertex Crease Patterns
      3. 12.3 Continuous Single-Vertex Foldability
    4. 13. General Crease Patterns
      1. 13.1 Local Flat Foldability is Easy
      2. 13.2 Global Flat Foldability is Hard
    5. 14. Map Folding
      1. 14.1 Simple Folds
      2. 14.2 Rectangular Maps: Reduction to 1D
      3. 14.3 Hardness of Folding Orthogonal Polygons
      4. 14.4 Open Problems
    6. 15. Silhouettes and Gift Wrapping
      1. 15.1 Strip Folding
      2. 15.2 Hamiltonian Triangulation
      3. 15.3 Seam Placement
      4. 15.4 Efficient Foldings
    7. 16. The Tree Method
      1. 16.1 Origami Bases
      2. 16.2 Uniaxial Bases
      3. 16.3 Everything is Possible
      4. 16.4 Active Paths
      5. 16.5 Scale Optimization
      6. 16.6 Convex Decomposition
      7. 16.7 Overview of Folding
      8. 16.8 Universal Molecule
    8. 17. One Complete Straight Cut
      1. 17.1 Straight-Skeleton Method
      2. 17.2 Disk-Packing Method
    9. 18. Flattening Polyhedra
      1. 18.1 Connection to Part III: Models of Folding
      2. 18.2 Connection to Fold-and-Cut Problem
      3. 18.3 Solution via Disk Packing
      4. 18.4 Partial Solution via Straight Skeleton
    10. 19. Geometric Constructibility
      1. 19.1 Trisection
      2. 19.2 Huzita’s Axioms and Hatori’s Addition
      3. 19.3 Constructible Numbers
      4. 19.4 Folding Regular Polygons
      5. 19.5 Generalizing the Axioms to Solve All Polynomials?
    11. 20. Rigid Origami and Curved Creases
      1. 20.1 Folding Paper Bags
      2. 20.2 Curved Surface Approximation
      3. 20.3 David Huffman’s Curved-Folds Origami
  11. Part III: Polyhedra
    1. 21. Introduction and Overview
      1. 21.1 Overview
      2. 21.2 Curvature
      3. 21.3 Gauss-Bonnet Theorem
    2. 22. Edge Unfolding of Polyhedra
      1. 22.1 Introduction
      2. 22.2 Evidence for Edge Unfoldings
      3. 22.3 Evidence against Edge Unfoldings
      4. 22.4 Unfoldable Polyhedra
      5. 22.5 Special Classes of Edge-Unfoldable Polyhedra
      6. 22.6 Vertex Unfoldings
    3. 23. Reconstruction of Polyhedra
      1. 23.1 Cauchy’s Rigidity Theorem
      2. 23.2 Flexible Polyhedra
      3. 23.3 Alexandrov’s Theorem
      4. 23.4 Sabitov’s Algorithm
    4. 24. Shortest Paths and Geodesics
      1. 24.1 Introduction
      2. 24.2 Shortest Paths Algorithms
      3. 24.3 Star Unfolding
      4. 24.4 Geodesics: Lyusternik–Schnirelmann
      5. 24.5 Curve Development
    5. 25. Folding Polygons to Polyhedra
      1. 25.1 Folding Polygons: Preliminaries
      2. 25.2 Edge-to-Edge Gluings
      3. 25.3 Gluing Trees
      4. 25.4 Exponential Number of Gluing Trees
      5. 25.5 General Gluing Algorithm
      6. 25.6 The Foldings of the Latin Cross
      7. 25.7 The Foldings of a Square to Convex Polyhedra
      8. 25.8 Consequences and Conjectures
      9. 25.9 Enumerations of Foldings
      10. 25.10 Enumerations of Cuttings
      11. 25.11 Orthogonal Polyhedra
    6. 26. Higher Dimensions
      1. 26.1 Part I
      2. 26.2 Part II
      3. 26.3 Part III
  12. Bibliography
  13. Index