How can linkages, pieces of paper, and polyhedra be folded? The authors present hundreds of results in this comprehensive look at the mathematics of folding. A proof shows that it is possible to design a series of jointed bars moving only in a flat plane that can sign a name or trace any other algebraic curve. One remarkable algorithm shows you can fold any straight-line drawing on paper so that the complete drawing can be cut out with one straight scissors cut. Aimed primarily at advanced undergraduate and graduate students in mathematics or computer science, this lavishly illustrated book will fascinate a broad audience, from high school students to researchers.
Demailly J.-P., Tian G., Peternell T.
presents hundreds of results and more than 60 unsolved “open problems” to spur further research.
to 23 different convex polyhedra.
fascinate a broad audience, from high school students to researchers.
Spira Award for Distinguished Teaching, and the NSERC Doctoral Prize.
influential recreational mathematician Martin Gardner.
Geometric folding algorithms : linkages, origami, polyhedra / Erik D.
1. Polyhedra – Models. 2. Polyhedra – Data processing.
I. O’Rourke, Joseph. II. Title.
Generalizing the Axioms to Solve All Polynomials?
amino acid sequence, the venerable “protein folding problem.” The second question (flattening) is relevant to the design of automobile airbags.
sheet and folding it with a bending machine.
the topics covered, we restrict ourselves here to meta-issues.
sophistication” will make accessible at least three-quarters of the book.
and dynamic programming); and aspects of complexity theory, especially the theory of NP-completeness. In general the material is elementary, though it is sometimes challengingly intricate.
easily form the core of an undergraduate or graduate course.
was being written. Please check the book’s Web site1 for the latest status.
Marshall Bern, Therese Biedl, David Bremner, Patricia Cahn, Jason H.
Cantarella, Roxana Cocan, Robert Connelly, Mirela Damian, Martin L.
http://www.gfalop.org; see also http://cs.smith.edu/∼orourke/TOPP for several of the most prominent open problems.
Whitesides, and Jianyuan K. Zhong.
Schlickenrieder, Don Shimamoto, Amanda Toop, and Emily Zaehring.
creative help and extensive support throughout the project.
followed in the book, but it serves to place related material nearby.
as instances of “reconfiguration” between two states.
that the motion of some free joint J traces out precisely S ?
version of this collection of curves.
The surprising answer is yes, even if the “curve” includes cusps and multiple pieces.
Thus, there is linkage that “signs your name” (Figure 0.1).
as the mule deer shown in Figure 0.2.
state, this has yet to be formally proved.
example from his Painter’s Manual (1525).
gallery/gallery.php4?name=mule deer The crease pattern was designed using TreeMaker.
Figure 0.3. A net for the snub cube, drawn by Dürer.
is known to be yes (Section 24.3).
We now make our second pass through the three parts of the book, this time concentrating on foldability.
its total length is ≤ L?
throughout the book that establish similar NP-completeness results.
valley crease, can it be folded into a single 1 × 1 square?
that cannot be folded (Justin 1994).
polyhedron of 16 triangular faces.
problem may make this tractable even though the unconstrained problem is not.
Given a polygon of n vertices, can it fold to some convex polyhedron?
can be decided in polynomial time.
plunging into the details, which we now proceed to do.
the community for at least a decade: deciding under what condition a chain is locked.
to protein folding in Chapter 9.
We now turn to classifying the problems pursued in later chapters.
in figures, but in our analysis assume all joints are mutual endpoints.
joints are pinned to the plane. The shaded “lamp’’ structure is rigid (because of the interior diagonals).
many details deferred to later sections.
called a polygon; one whose graph is a path we will call a polygonal chain or just a chain.
In the literature a chain is also called an arc, a robot arm, or an arm.
and often use planar to mean 2D.
for different linkage structures, which will be detailed later (in Chapter 6).
example, the number of constant-degree piecewise-algebraic arcs composing the path.
use the term “realization” for a different notion in Chapter 4.
This is also called the moduli space of the linkage.
Refer ahead to page 22 for a brief tutorial on complexity classes.
The roots of this idea go back to Lozano-Pérez and Wesley (1979).
and doubled by point z.
from overhead cables, in the design of tool box drawers, and in many other applications.
Their ability to translate a motion will be used in Section 3.2.
Three manufacturing processes lead to interesting folding questions: sheet-metal bending, pipe bending, and box folding.
intermediate “workpiece” and both itself and the machine parts becomes a challenge.
as a function of the number of bends n.
sequence) that avoids part self-intersection is an intractable problem9 for both sheetmetal bending and pipe bending.
space, which is, for their examples, as large as 9D.
for reasons to be explained in Section 8.1) between each pair of incident links.
chains,” for bond angles are nearly fixed (Section 8.1).
“One of the great challenges of molecular biochemistry and biology” (Troyer et al. 1997).
apology for addressing theoretical questions for their own sake.
angles θ 1 and θ 2 , each with wrap-around ranges [0, 2π ] (see p. 61).
stating the result more precisely.
that a configuration can be represented by a point in Rk .
d, the maximum algebraic (polynomial) degree of the constraint surfaces.
Reprinted in Hopcroft et al. (1987).
a general motion planning algorithm with time complexity O(m k+1 d O(k ) ) (see Box 2.2).
coordinated motion of several robots and/or mechanisms is especially rich topologically (Abrams and Shrist 2002). However, we focus primarily on the simplest spaces.
apply. So instead let us say that k = 2n, using two Cartesian coordinates for each joint.
Analyzed in Alt et al. (2004) and in Connelly and Demaine (2004).
polynomials, a CAD is realized by a partition of R1 at the real roots of the polynomials.
recursion leads to a doubly exponential number of cells: O((md )3 ).
The randomization is needed only to choose a generic direction for coordinate axes.
critical points. Motion planning is then reduced to searching the roadmap.
complexity, O(m k+1 d O(k ) ).
the coordinates of the four endpoints.3 All equations have degree at most 2, so d = 2.
of O(n4n−2 2 O(n ) ) = 2 O(n ) .
For example, see the formulation in terms of signed areas of triangles in (O’Rourke 1998, Ch. 1).
these results determine the complexity of these problems as PSPACE-complete.
will sketch below. This path specifies a continuous reconfiguration from A to B.
and then can be constructed as above.
consist of more than one connected component?
each cell and arcs for adjacency, and searches this graph, say using depth-first search.
Connectivity in the graph leads to a path in configuration space.
Figure 2.2. Wooden “Hedgehog in a Cage” puzzle.
example before turning to lower bounds.
specific puzzle, the parameters are constant.
to establish complexity bounds (see, for example, O’Rourke 1998, Section 8.7).
history before describing the constructions.
in PSPACE, the problem is PSPACE-complete.
P ⊆ NP ⊆ PSPACE ⊆ EXP.
P ⊆ NP-complete ⊆ NP-hard ⊆ PSPACE-complete ⊆ PSPACE-hard ⊆ EXP.
object, unless P = PSPACE (and in particular P = NP).
easier than in 3D. Reif’s proof uses both the tree structure and 3D in essential ways.
reachability question for a planar graph-linkage, without obstacles and permitting selfintersections, is PSPACE-hard (Hopcroft et al. 1984). In a second paper (Hopcroft et al.
that reachability, in the presence of many obstacles, is PSPACE-complete.
PSPACE-complete. Second, the same problem for a chain in 3D is PSPACE-complete.
details to be explained shortly.
specified configurations in the absence of obstacles. The reason for omitting this problem is that here the answer is always yes! This lockability issue is the topic of Chapter 6.
course and reach the “exit.” See Figure 2.3 for one (small) section of the obstacle course.
of the input length (“space-bounded”), and the state transition graph is undirected (“symmetric”).
Figure 2.3. The movable object P consists of a series of identical tetrahedra linked by segments.
obstacles. See Figure 2.4 for a portion of their construction.
As mentioned earlier, this thread of research was resumed most recently by Alt et al.
this line of research: deciding the reconfigurability of an open chain in 3D is PSPACEcomplete.
later proofs. It is the only one we present in detail.
angle is either 0 or π – so that its total folded length is ≤ L?
Theorem 2.2.1 (Hopcroft et al. 1985). The ruler folding problem is NP-complete.
(0 , 1 , 2 , . . . , n+1 , n+2 , n+3 ) = (2s, s, x1 , . . . , xn , s, 2s).
of partition has the answer yes.
Figure 2.5. Ruler folding reduction. Here x1 + x3 + x4 = x2 + x5 + x6 .
that length. So we have established the claim for L = 2s.
Recently a “fully polynomial-time approximation scheme”7 has been found for finding the minimum folding length of a ruler (Cǎlinescu and Dumitrescu 2005).
be folded to length ≤ k.
(200L)2 + 1, and C has length 200L + 1, more than enough to reach p.
output sizes of the problem.
Figure 2.6. (a) Initial configuration. The dashed segment starting from v0 represents a large collection of unit links. The slashes indicate interruptions. Note the tunnel is only 2 + ε units high.
(b) Intermediate configuration, when R100 is folded and about to pass through the gap.
fact, linear) in n; what is difficult is finding the moves.
Theorem 2.2.2 (line 3 of Table 2.1) drops the complexity from NP-hard to O(n)!
by Kapovich and Millson (2002).
configuration space of a planar linkage.
and deformed into the other.
whose “orbit” follows any given algebraic curve) in Section 3.2.
is to explain Kempe’s universality theorem 3.2.1.
of the design of linkages to draw straight lines, which led directly to Kempe’s work.
We rely here primarily on Kempe (1877).
“it was the most beautiful thing he had ever seen” (Fergusson 1962).
Hunt (1978, p. 134), quoting Reuleaux from 1875.
Koetsier (1999) and Kempe (1877, p. 12).
it in one position, the light lines in another.
There is a linkage that signs your name.
followed by a discussion of the flaw and one route to repair.
with linkages is similar: His proof was flawed, but the overall conception was brilliant.
There has since been an extension to 3D (Zindler 1931).
y = a cos(α − π/2) + b cos(β − π/2).
+ 2a 2 b cos β + b3 cos β − b3 cos(3 β) − 3a 2 b cos(2 α + β) − 3ab 2 cos(α + 2 β) .
of the form ri α + si β + δi from α and β.
thus both are necessary. Hence, we describe these gadgets in reverse order.
adjacent sides of a parallelogram across the diagonal they determine (see Figure 3.4).
Figure 3.5. Kempe’s “multiplicator”: two nested, similar contraparallelograms.
Figure 3.6. Kempe’s angle trisector (Kempe 1877, p. 42).
In this case, the xy rod is redundant. So j = 2 and r = 3, and 2 j − r = 1.
does B to B  ; (b) the construction with superimposed reversors.
return to this point in Part II, Chapter 19 (p. 285).
as illustrated in Figure 3.7(a). A makes an angle α with C and reflects across C to A  .
the angle θ 1 with link B and θ 2 with link B  , and then A reads off the “output” θ 1 + θ 2 .
and joints are shown shaded in Figure 3.7(b).
that is, the annulus of reachability for the point y (according to Theorem 5.1.2) is a disk.
There is, however, a flaw in this design, to which we will return below.
provided by the parallelogram linkage in Figure 3.3 (see Figure 3.9).
Another term for the configuration space of the linkage.
Figure 3.10. Simulating a joint in the interior of a link.
and get rid of undesirable configurations (p. 3).
of Abbott and Barton (2004).
only at endpoints of bars and simulate an interior joint as follows. Refer to Figure 3.10.
due to Abbott and Barton (2004).
Figure 3.11. (a–c) Three circular motions of a rhombus; (d) rhombus rigidified.
long enough, this is impossible. See Box 3.1 for details.
p, q, r , and s are collinear.
x is on the perpendicular bisector of sq and on the perpendicular bisector of pr .
|sp| · |sr | = 14 (|ab|2 − |ad|2 ).
the configuration space of linkages.
offer strong evidence that these bounds are optimal.
C in the plane, is there is a linkage that traces exactly that curve via a continuous motion/reconfiguration?
and |b c| = |da|, so that abcd is a contraparallelogram.
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.
configuration to trace different sections of C.