More Like this

1. Face flips in origami tessellations

   Akitaya, Hugo A ; Dujmović, Vida ; Eppstein, David ; Hull, Thomas C ; Jain, Kshitij ; Lubiw, Anna ( January 2020 , Journal of computational geometry)

   null (Ed.)

   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 where $\mu_F$ results in a MV assignment that is either never, sometimes, or always locally flat-foldable, for various choices of $F$. We also consider the problem of finding, given two locally flat-foldable MV assignments $\mu_1$ and $\mu_2$ of a given crease pattern $G$, a minimal sequence of face flips to turn $\mu_1$ into $\mu_2$. We find polynomial-time algorithms for this in the cases where $G$ is either a square grid or the Miura-ori, and show that this problem is NP-complete in the case where $G$ is the triangle lattice. 

   more » « less
2. On the approximability of random-hypergraph MAX-3-XORSAT problems with quantum algorithms

   Eliot Kapit, Brandon A. ( December 2023 , arXivorg)

   Constraint satisfaction problems are an important area of computer science. Many of these problems are in the complexity class NP which is exponentially hard for all known methods, both for worst cases and often typical. Fundamentally, the lack of any guided local minimum escape method ensures the hardness of both exact and approximate optimization classically, but the intuitive mechanism for approximation hardness in quantum algorithms based on Hamiltonian time evolution is poorly understood. We explore this question using the prototypically hard MAX-3-XORSAT problem class. We conclude that the mechanisms for quantum exact and approximation hardness are fundamentally distinct. We qualitatively identify why traditional methods such as quantum adiabatic optimization are not good approximation algorithms. We propose a new spectral folding optimization method that does not suffer from these issues and study it analytically and numerically. We consider random rank-3 hypergraphs including extremal planted solution instances, where the ground state satisfies an anomalously high fraction of constraints compared to truly random problems. We show that, if we define the energy to be E=Nunsat−Nsat, then spectrally folded quantum optimization will return states with energy E≤AEGS (where EGS is the ground state energy) in polynomial time, where conservatively, A≃0.6. We thoroughly benchmark variations of spectrally folded quantum optimization for random classically approximation-hard (planted solution) instances in simulation, and find performance consistent with this prediction. We do not claim that this approximation guarantee holds for all possible hypergraphs, though our algorithm's mechanism can likely generalize widely. These results suggest that quantum computers are more powerful for approximate optimization than had been previously assumed. 

   more » « less
3. Enabling Robust Self‐Folding Origami by Pre‐Biasing Vertex Buckling Direction

   https://doi.org/10.1002/adma.201903006  

   Kang, Ji‐Hwan ; Kim, Hyunki ; Santangelo, Christian D. ; Hayward, Ryan C. ( August 2019 , Advanced Materials)

   Self‐folding is a powerful approach to fabricate materials with complex 3D forms and advanced properties using planar patterning steps, but suffers from intrinsic limitations in robustness due to the highly bifurcated nature of configuration space around the flat state. Here, a simple mechanism is introduced to achieve robust self‐folding of microscale origami by separating actuation into two discrete steps using different thermally responsive hydrogels. First, the vertices are pre‐biased to move in the desired direction from the flat state by selectively swelling one of the two hydrogels at high temperature. Subsequently, the creases are folded toward their target angles by activating swelling of the second hydrogel upon cooling to room temperature. Since each vertex can be individually programmed to move upward or downward, it is possible to robustly select the desired branch even in multi‐vertex structures with reasonably high complexity. This strategy provides key new principles for designing shaping‐morphing materials that avoid undesired distractor states, expanding their potential applications in areas such as soft robotics, sensors, mechanical metamaterials, and deployable devices.

    

   more » « less
4. OPTIMAL DESIGN FOR DEPLOYABLE STRUCTURES USING ORIGAMI TESSELLATIONS

   https://doi.org/10.1115/IMECE2019-11062  

   Cardona, Carolina ; Tovar, Andres ; Anwar, Sohel ( November 2019 , Proceedings of the ASME International Mechanical Engineering Congress and Exposition)

   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 this unit cell allows us to create tessellations that are used in the creation of deployable shelters. Design requirements for structurally sound tessellations are discussed and used to evaluate the effectiveness of our results. Future work includes the applications of unit cells and tessellation design for origami inspired mechanisms. Special focus will be given to self-deployable structures, including shelters for natural disasters. 

   more » « less
5. On the impact of running intersection inequalities for globally solving polynomial optimization problems

   https://doi.org/10.1007/s12532-019-00169-z  

   Del Pia, Alberto ; Khajavirad, Aida ; Sahinidis, Nikolaos V. ( August 2019 , Mathematical Programming Computation)

   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 facet-defining 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 NP-hard. Subsequently, for multilinear polytopes of fixed degree, we devise an efficient polynomial-time algorithm for separating running intersection inequalities and embed the proposed cutting-plane generation scheme at every node of the branch-and-reduce global solver BARON. To evaluate the effectiveness of the proposed method we consider two test sets: randomly generated multilinear and polynomial optimization problems of degree three and four, and computer vision instances from an image restoration problem Results show that running intersection cuts significantly improve the performance of BARON and lead to an average CPU time reduction of 50% for the random test set and of 63% for the image restoration test set. 

   more » « less