Folding and Unfolding in Computational Geometry

Part I: Linkages

Last Update:

All material in these pages is Copyright 2006 by Erik D. Demaine and Joseph O'Rourke.

Note: The contents list below is out-of-date w.r.t. the final contents, for which see TOC.

1. Classification
   • desk lamp
2. Applications
   • Robotics
   • Mechanisms
   • Bending Machines
   • Protein Folding
   • Mathematical Aesthetics
3. General Algorithms and Upper Bounds
   • Configuration and Space Approach
     • Specialization to planar robot arms
     • Solving Problems with Configuration Spaces
   • Example: Separation Puzzles
4. Lower Bounds
   • Introduction
   • Three Constructions Sketched
   • Straight-line Linkages
     • Degrees of Freedom
     • Watt Parallel Motion
     • Peaucellier Linkage
   • Kempe's University Theorem
     • Linkage Parallelogram
     • Contraparallelogram
     • Kempe's Multiplicator
     • Kempe's Additor
     • The Flaw and a Repair
   • Hart's Inversor
5. Rigid Frameworks
   • History
   • Rigidity
   • Generic Rigidity
     • Laman's Theorem
     • Higher dimentions
     • Henneberg Constructions
   • Infinitesimal Rigidity
     • Infinitesimal Length Constraint
     • Rigidity Matrix
       • Square
     • Connection between Rigidity and Infinitestimal Rigidity
   • Tensegrities
     • Infinitesimal Rigidity
     • Connection to Linear Programming
     • Stress
     • Duality
     • Linkages and Tensegrities
   • Polyhedral Liftings
6. Reconfiguration Permitting Intersection
   • Chain Reachability
     • Annulus
     • Two-Kinks Theorem
     • Solving a 3-link problem
     • Turning a Polygon Inside-Out
       • Line Tracking
7. Reconfiguration of Chains in Confined Regions
   • Chains Confined to Circles
   • Chains Confined to Squares
   • Chains Confined to Equilateral Triangles
8. Reconfiguration of Chains without Self-Crossing
   • 2D: Convex Polygons
     • Quadrangle
   • 2D/3D:Arbitrary Polygons
     • Pocket Flipping
     • Deflations
     • Variations on Flipping
     • Arch Algorithms
       • AGP Algorithm
   • 3D: Simple Projection
9. Locked Chains
   • Introduction
   • History
   • Locked Chains in 3D
     • Locked Open Chains
   • Locked Closed Chains
   • No Locked Chains in 4D
   • Locked Trees in 2D
   • No Locked Chains in 2D (To Erik Demaine's Linkage Page)
     • Expansiveness and the Connection to Tensegrities
     • Combinatorial Argument
   • Algorithms for Unlocking 2D Chains
     • Unlocking 2D Chains using Differential Equations
     • Unlocking 2D Chains using Pseudotriangulations
     • Unlocking 2D Chains using Energy
   • Infinitesimally Locked Linkages in 2D
     • Stronger Definitions of Locked
     • Self-Touching Configurations
       • Connection to Rigidity
       • Proving Trees Locked
   • 3D Polygons with a Simple Projection
10. Interlocked Chains
    • 2-chains
    • 3-chains
      • Example:An open 3-chain cannot lock with a triangle
    • 4-chains
11. Joint-Constrained Motion
    • Fixed-Angle Linkages
      • Extreme Spans
      • Flattening
      • Flat-State Connectivity
      • Flat-State Disconnected Linkages
      • Partially Rigid Orthogonal Tree
      • Orthogonal Graph
      • Open Orthogonal Chains
      • Multiple Pinned Orthogonal Open Chains
    • Convex Chains
      • Cauchy's Arm Lemma
        • Cauchy opening
      • Uses and Generalizations of Cauchy's Lemma
      • Straightening Convex Chains
12. Protein Folding
    • Producible Polygonal Protein Chains
      • Open Problems on Equilateral Chains
    • Probabilistic Road Maps
    • H-P Model
      • NP-completeness
      • Unique Optimal Foldings