Face flips in origami tessellations

Abstract

Given a flat-foldable origami crease pattern $G=(V,E)$ (a straight-line drawing of a planar graph on a region of 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 for a variety of crease patterns $G$ that are tilings of the plane, proving examples where ${\mu }_F$ results in a MV assignment that is either never, sometimes, or always flat-foldable for various choices of $F$. We also consider the problem of finding, given two 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-hard in the case where $G$ is the triangle lattice.