Rigid foldability is NP-hard
In this paper, we show that the rigid-foldability of a given crease pattern using all creases is weakly NP-hard by a reduction from the partition problem, and that rigid-foldability with optional creases is NP-hard by a reduction from the 1-in-3 SAT problem. Unlike flat-foldabilty of origami or flexibility of other kinematic linkages, whose complexity originates in the complexity of the layer ordering and possible self-intersection of the material, rigid foldabilltiy from a planar state is hard even though there is no potential self-intersection. In fact, the complexity comes from the combinatorial behavior of the different possible rigid folding configurations at each vertex. The results underpin the fact that it is harder to fold from an unfolded sheet of paper than to unfold a folded state back to a plane, frequently encountered problem when realizing folding-based systems such as self-folding matters and reconfigurable robots.
Authors:
; ; ; ; ;
Award ID(s):
Publication Date:
NSF-PAR ID:
10209599
Journal Name:
Journal of computational geometry
Volume:
11
Issue:
1
Page Range or eLocation-ID:
93–124
ISSN:
1920-180X
1. Given a locally flat-foldable origami crease pattern $G=(V,E)$ (a straight-line drawing of a planar graph on the plane) with a mountain-valley (MV) assignment $\mu:E\to\{-1,1\}$ indicating which creases in $E$ bend convexly (mountain) or concavely (valley), we may \emph{flip} a face $F$ of $G$ to create a new MV assignment $\mu_F$ which equals $\mu$ except for all creases $e$ bordering $F$, where we have $\mu_F(e)=-\mu(e)$. In this paper we explore the configuration space of face flips that preserve local flat-foldability of the MV assignment for a variety of crease patterns $G$ that are tilings of the plane. We prove examples wheremore »