Geometric Folding Algorithms
Nadia M. Benbernou, Erik D. Demaine, Martin L. Demaine
The area of geometric folding and unfolding is attractive in that problems
and even results can be easily understood with little knowledge of mathematics
or computer science, yet the solutions are difficult and involve many
sophisticated techniques. The general form of a folding problem is to
determine how a particular geometric object (e.g., linkage, piece of paper,
polyhedron, or protein) can be reconfigured or folded according
to a few constraints, which depend on the object being folded and the
problem of interest. In particular, we are interested in characterizing
the existence of foldings, and efficient algorithms for finding foldings,
or in proving that such algorithms are impossible.
Most folding and unfolding problems are attractive from a pure mathematical
standpoint, for the beauty of the problems themselves. Nonetheless, most
of the problems have close connections to important industrial applications.
Linkage folding has applications in robotics and hydraulic tube bending,
and has connections to protein folding. Paper folding has applications
in sheet-metal bending, packaging, and air-bag folding. Unfolding polyhedra
has applications in manufacturing, particularly sheet-metal bending.
In various collaborations, we have solved a variety of folding problems.
Here we describe a few of the more recent results:
- Producible protein chains [DLO06]. Fixed-angle polygonal
chains in 3D serve as an interesting model of protein backbones. Here
we consider such chains produced by a ribosome, modeled crudely as a
cone, and examine the constraints this model places on the producible
chains. We prove as our main result that a chain whose maximum turn
angle is α is producible in a cone of half-angle ≥ α
if and only if the chain is flattenable, that is, the chain can be reconfigured
without self-intersection to lie flat in a plane. This result establishes
that two seemingly disparate classes of chains are in fact identical.
Along the way, we discover that all producible configurations of a chain
can be moved to a canonical configuration resembling a helix.
- Maximum span of fixed-angle chains [Ben06, BO07].
Soss proved that it is NP-hard to find the maximum flat span of a fixed-angle
polygonal chain: the largest distance achievable between the endpoints
in a planar embedding [Sos01]. We show that, in polynomial time, we
can find the maximum 3D span of a fixed-angle chain in two special
cases of particular relevance to proteins. First, when all link lengths
are equal and all joint angles are equal, the maximum 3D span is achieved
in a flat configuration and can be computed in constant time. Second,
when all angles are equal (but the link lengths arbitrary), the maximum
3D span is in general nonplanar but can be found in O(n2)
- Energy-driven approach to linkage unfolding [CDIO04].
We present a new algorithm for unfolding planar polygonal linkages without
self-intersection based on following the gradient flow of a “repulsive”
energy function. This algorithm has several advantages over previous
methods. (1) The output motion is represented explicitly and exactly
as a piecewise-linear curve in angle space. As a consequence, an exact
snapshot of the linkage at any time can be extracted from the output
in strongly polynomial time (on a real RAM supporting arithmetic, radicals,
and trigonometric functions). (2) Each step of the motion can be
computed exactly in O(n2) time on a real RAM
where n is the number of vertices. (3) We explicitly bound
the number of linear steps (and hence the running time) as a polynomial
in n and the ratio between the maximum edge length and the initial
minimum distance between a vertex and an edge. (4) Our method is
practical and easy to implement. We provide a publicly
accessible Java applet that implements the algorithm.
- Flat-state connectivity of fixed-angle linkages [ADD+02,
ADM+02]. We explore which classes of linkages in 3D have the
property that each pair of their flat states—that is, their embeddings
in 2D without self-intersection—can be connected by a continuous
dihedral motion that avoids self-intersection throughout. Dihedral motions
preserve all angles between pairs of incident edges, which is most natural
for protein models. Our positive results include proofs that open chains
with nonacute angles are flat-state connected, as are closed orthogonal
unit-length chains. Among our negative results is an example of an orthogonal
graph linkage that is flat-state disconnected. Several additional results
are obtained for other restricted classes of linkages.
- Infinitesimally locked linkages [CDR02]. We propose
a new algorithmic approach for analyzing whether planar linkages are
locked in the sense that they cannot be moved into some other configuration
while preserving the bar lengths and not crossing any bars. The idea
is to examine self-touching or degenerate frameworks in which multiple
edges converge to geometrically overlapping configurations. We show
how to study whether such frameworks are locked using techniques from
rigidity theory, in particular first-order rigidity and equilibrium
stresses. Then we show how to relate locked self-touching frameworks
to locked frameworks that closely approximate the self-touching frameworks.
Our motivation is that most existing approaches to locked linkages are
based on approximations to self-touching frameworks. In particular,
we show that a previously proposed locked tree in the plane [BDD+02]
can be easily proved locked using our techniques, instead of the tedious
arguments required by standard analysis. We also present a new locked
tree in the plane with only one degree-3 vertex and all other vertices
degree 1 or 2. This tree can also be easily proved locked with
our methods, and implies that the result about unfolding polygonal arcs
and cycles [CDR03] is the best possible.
- Short interlocked linkages [DLOS02, DLOS03]. We
study collections of linkages in 3-space that are interlocked
in the sense that the linkages cannot be separated without one bar crossing
through another. We explore pairs of linkages, one open chain and one
closed chain, each with a small number of joints, and determine which
can be interlocked. In particular, we show that a triangle and an open
4-chain can interlock, a quadrilateral and an open 3-chain can interlock,
but a triangle and an open 3-chain cannot interlock. We also consider
pairs of open chains of bars connected with rigid joints, revolute joints,
or universal joints, and explore the smallest number of chains and bars
needed to achieve interlock.
- Map folding [ABD+04]. We explore the following formulation
of the map-folding problem: given a collection of creases on a piece
of paper, each assigned a folding direction of mountain or valley, is
there a flat folding by a sequence of simple folds? There are several
models of simple folds; the simplest one-layer simple fold
rotates a portion of paper about a crease in the paper by ±180°.
We first consider the analogous questions in one dimension lower—bending
a segment into a flat object—which lead to interesting problems
on strings. We develop efficient algorithms for the recognition of simply
foldable 1D crease patterns, and reconstruction of a sequence of simple
folds. Indeed, we prove that a 1D crease pattern is flat-foldable by
any means precisely if it is by a sequence of one-layer simple folds.
In addition to the several folding problems that remain unsolved, Erik
Demaine and Joseph O'Rourke (Smith College) are publishing a book, Geometric
Folding Algorithms: Linkages, Origami, Polyhedra with Cambridge
University Press, in May–June 2007.
This research is partially supported by NSF CAREER award CCF-0347776
and DOE grant DE-FG02-04ER25647.
- Greg Aloupis, Erik D. Demaine, Vida Dujmović, Jeff Erickson,
Stefan Langerman, Henk Meijer, Ileana Streinu, Joseph O'Rourke, Mark
Overmars, Michael Soss, and Godfried T. Toussaint. Flat-state
connectivity of linkages under dihedral motions. In Proceedings
of the 13th Annual International Symposium on Algorithms and Computation,
pp. 369–380, Vancouver, Canada, November 2002.
- Greg Aloupis, Erik D. Demaine, Henk Meijer, Joseph O'Rourke, Ileana
Streinu, and Godfried Toussaint. Flat-state
connectedness of fixed-angle chains: Special acute chains. In Proceedings
of the 14th Canadian Conference on Computational Geometry, pp.
27–30, Lethbridge, Canada, August 2002.
- Esther M. Arkin, Michael A. Bender, Erik D. Demaine, Martin L. Demaine,
Joseph S. B. Mitchell, Saurabh Sethia, and Steven S. Skiena. When
can you fold a map? Computational Geometry: Theory and Applications
29(1):23–46, September 2004.
- Nadia Benbernou. Fixed-angle polygonal chains: Locked chains and
the maximum span. Undergraduate thesis, Smith College, 2006.
- Nadia Benbernou and Joseph O'Rourke. On the maximum span of fixed-angle
chains. Computational Geometry: Theory and Applications, to
- Therese Biedl, Erik Demaine, Martin Demaine, Sylvain Lazard, Anna
Lubiw, Joseph O'Rourke, Steve Robbins, Ileana Streinu, Godfried Toussaint,
and Sue Whitesides. A
note on reconfiguring tree linkages: Trees can lock. Discrete
Applied Mathematics, 117(1–3):293–297, 2002.
- Jason H. Cantarella, Erik D. Demaine, Hayley N. Iben, and James F.
energy-driven approach to linkage unfolding. In Proceedings
of the 20th Annual ACM Symposium on Computational Geometry, pp.
134–143, Brooklyn, New York, June 2004.
- Robert Connelly, Erik D. Demaine, and Günter Rote. "Infinitesimally
locked self-touching linkages with applications to locked trees.
In J. Calvo, K. Millett, and E. Rawdon, editors, Physical Knots:
Knotting, Linking, and Folding of Geometric Objects in 3-space,
pp. 287–311. American Mathematical Society, 2002.
- Robert Connelly, Erik D. Demaine, and Günter Rote. Straightening
polygonal arcs and convexifying polygonal cycles. Discrete &
Computational Geometry, 30(2):205–239, September 2003.
- Erik D. Demaine, Stefan Langerman, and Joseph O'Rourke. Geometric
restrictions on producible polygonal protein chains. Algorithmica
44(2):167–181, February 2006.
- Erik D. Demaine, Stefan Langerman, Joseph O'Rourke, and Jack Snoeyink.
open linkages with few joints. In Proceedings of the 18th Annual
ACM Symposium on Computational Geometry, pp. 189–198, Barcelona,
Spain, June 2002.
- Erik D. Demaine, Stefan Langerman, Joseph O'Rourke, and Jack Snoeyink.
open and closed linkages with few joints. Computational Geometry:
Theory and Applications, 26(1):37–45, August 2003.
- Michael Soss. Geometric and computational aspects of molecular
reconfiguration. Ph.D. thesis, School Comput. Sci., McGill Univ.,