Given a locally flatfoldable origami crease pattern $G=(V,E)$ (a straightline drawing of a planar graph on the plane) with a mountainvalley (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 flatfoldability of the MV assignment for a variety of crease patterns $G$ that are tilings of the plane. We prove examples wheremore »
Rigid foldability is NPhard
In this paper, we show that the rigidfoldability of a given crease pattern using all creases is weakly NPhard by a reduction from the partition problem, and that rigidfoldability with optional creases is NPhard by a reduction from the 1in3 SAT problem. Unlike flatfoldabilty of origami or flexibility of other kinematic linkages, whose complexity originates in the complexity of the layer ordering and possible selfintersection of the material, rigid foldabilltiy from a planar state is hard even though there is no potential selfintersection. 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 foldingbased systems such as selffolding matters and reconfigurable robots.
 Award ID(s):
 1906202
 Publication Date:
 NSFPAR ID:
 10209599
 Journal Name:
 Journal of computational geometry
 Volume:
 11
 Issue:
 1
 Page Range or eLocationID:
 93–124
 ISSN:
 1920180X
 Sponsoring Org:
 National Science Foundation
More Like this


This work presents innovative origami optimization methods for the design of unit cells for complex origami tessellations that can be utilized for the design of deployable structures. The design method used to create origami tiles utilizes the principles of discrete topology optimization for ground structures applied to origami crease patterns. The initial design space shows all possible creases and is given the desired input and output forces. Taking into account foldability constraints derived from Maekawa's and Kawasaki's theorems, the algorithm designates creases as active or passive. Geometric constraints are defined from the target 3D object. The periodic reproduction of thismore »

We consider global optimization of nonconvex problems whose factorable reformulations contain a collection of multilinear equations. Important special cases include multilinear and polynomial optimization problems. The multilinear polytope is the convex hull of the set of binary points z satisfying the system of multilinear equations given above. Recently Del Pia and Khajavirad introduced running intersection inequalities, a family of facetdefining inequalities for the multilinear polytope. In this paper we address the separation problem for this class of inequalities. We first prove that separating flower inequalities, a subclass of running intersection inequalities, is NPhard. Subsequently, for multilinear polytopes of fixed degree,more »

The Minimum Circuit Size Problem (MCSP) has been the focus of intense study recently; MCSP is hard for SZK under rather powerful reductions, and is provably not hard under "local" reductions computable in TIME(n^0.49) . The question of whether MCSP is NPhard (or indeed, hard even for small subclasses of P) under some of the more familiar notions of reducibility (such as manyone or Turing reductions computable in polynomial time or in AC^0) is closely related to many of the longstanding open questions in complexity theory. All prior hardness results for MCSP hold also for computing somewhat weak approximations tomore »

Waiting at the right location at the right time can be critically important in certain variants of timedependent shortest path problems. We investigate the computational complexity of timedependent shortest path problems in which there is either a penalty on waiting or a limit on the total time spent waiting at a given subset of the nodes. We show that some cases are nondeterministic polynomialtime hard, and others can be solved in polynomial time, depending on the choice of the subset of nodes, on whether waiting is penalized or constrained, and on the magnitude of the penalty/waiting limit parameter. Summary ofmore »