Research Abstracts - 2007

What

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.

Progress

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(n²) time.
• 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(n²) 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.

Future

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.

Research Support

This research is partially supported by NSF CAREER award CCF-0347776 and DOE grant DE-FG02-04ER25647.

References

[ADD+02]

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.

[ADM+02]

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.

[ABD+04]

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.

[Ben06]

Nadia Benbernou. Fixed-angle polygonal chains: Locked chains and the maximum span. Undergraduate thesis, Smith College, 2006.

[BO07]

Nadia Benbernou and Joseph O'Rourke. On the maximum span of fixed-angle chains. Computational Geometry: Theory and Applications, to appear.

[BDD+02]

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.

[CDIO04]

Jason H. Cantarella, Erik D. Demaine, Hayley N. Iben, and James F. O'Brien. An 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.

[CDR02]

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.

[CDR03]

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.

[DLO06]

Erik D. Demaine, Stefan Langerman, and Joseph O'Rourke. Geometric restrictions on producible polygonal protein chains. Algorithmica 44(2):167–181, February 2006.

[DLOS02]

Erik D. Demaine, Stefan Langerman, Joseph O'Rourke, and Jack Snoeyink. Interlocked open linkages with few joints. In Proceedings of the 18th Annual ACM Symposium on Computational Geometry, pp. 189–198, Barcelona, Spain, June 2002.

[DLOS03]

Erik D. Demaine, Stefan Langerman, Joseph O'Rourke, and Jack Snoeyink. Interlocked open and closed linkages with few joints. Computational Geometry: Theory and Applications, 26(1):37–45, August 2003.

[Sos01]

Michael Soss. Geometric and computational aspects of molecular reconfiguration. Ph.D. thesis, School Comput. Sci., McGill Univ., 2001.