From one fold to another
If an origami crease pattern tells you where to put the folds, but not which way to fold them, you may have many choices left to make. A familiar example is the square grid. You can pleat (accordion-fold) the horizontal lines of the grid, and then pleat the resulting folded strip of paper along the vertical lines; the result will be that each horizontal line is consistently a mountain fold or a valley fold, but each vertical line has folds that alternate between mountain and valley. Or you could pleat the vertical lines first, and then the horizontal lines, getting a different folded state. There are many other choices beyond these two.
The famous Miura-ori is another grid-like fold made out of parallelograms instead of squares, and known for its ability to continuously unfold from its folded state to an expanded and completely open state. Like the square grid, a pattern of crease lines in the same positions has many alternative foldings. In fact, this multiplicity of folded states can be helpful in making the miura-ori out of paper. To make it, you can start with pleating a set of parallel lines (like the square grid) to form a folded strip of paper, and then pleat in a different direction that forms a non-right angle to the first pleating direction. The result will be a fold that is not the Miura-ori, but that has its folds in the same places as the Miura-ori. By reversing the orientation of some of these folds, you get the Miura-ori itself.
When working with the space of all foldings of a crease pattern, it’s unfortunately a bit complicated to understand which patterns fold flat (globally, as an entire structure) and which don’t. In a celebrated result from SODA 1996, Bern and Hayes showed that, for arbitrary crease patterns, even determining whether there exists a globally flat-foldable state is NP-complete. So it’s easier to work with “local flat foldings”, meaning a labeling of all of the creases as mountain or valley folds with the property that the creases surrounding each vertex of the folding pattern could be folded flat, if only all of that other stuff farther away from the vertex didn’t get in the way. It’s easy to check whether a single vertex can be folded flat using Maekawa’s theorem, Kawasaki’s theorem and related results.
In an earlier paper, my co-authors and I studied the space of all local flat foldings of the Miura-ori crease pattern, from the point of view of seeking forcing sets, mountain-valley assignments to small subsets of the creases with the property that there is only one way to extend them to a locally flat-foldable mountain-valley assignment on the whole crease pattern. My new preprint, “Face flips in origami tessellations” (with Akitaya, Dujmović, Hull, Jain, and Lubiw, arXiv:1910.05667) instead looks at the connectivity of the system of all local flat foldings. If you’re in one locally flat-folded state (say, the state that you get from pleating the paper once and then pleating the folded strip a second time in a non-orthogonal direction) and you want to get to a different flat-folded state (say, the Miura-ori itself), how many moves does it take? Here, we’re not just allowing any change of a single crease from mountain to valley or vice versa to count as a move. Instead, a move is what happens when you change all of the folds surrounding a single face of the crease pattern, in such a way that the new mountain-valley assignment remains flat-foldable.
The results vary dramatically according to the folding pattern. For the square grid, every square can be flipped, and given any two mountain-valley assignments you can color the squares black or white according to whether they are surrounded an even or odd number of times by cycles of creases that need to be changed. Then the shortest way to get from one assignment to the other is either to flip all the black squares or to flip all the white squares. For a grid of equilateral triangles, it is possible to flip from any mountain-valley assignment to any other one within a polynomial number of steps, but finding the shortest sequence is NP-complete. And for the Miura-ori, it’s again always possible, and there’s a nontrivial polynomial time algorithm for finding the shortest flip sequence. We also have examples of crease patterns forming periodic tilings of the plane where nothing is flippable (so the state space becomes totally disconnected) or where the flippable faces form an independent set (so you merely have to flip the faces whose surrounding mountain-valley assignments differ, in any order). The image below shows two crease patterns of the latter type (called square twist tessellations) with the flippable faces colored blue.
I think the results for the Miura-ori are particularly neat, so I want to outline them in a little more detail. There’s a natural bijection between local flat-foldings of the Miura crease pattern and 3-colorings of the squares of a square grid, which we used in the earlier paper, and flips of Miura faces correspond in the same way to recoloring steps in which we change the color of a single square. There’s also a natural correspondence (but not a bijection!) between 3-colorings of a grid and “height functions”, giving an integer height to each square, with each two adjacent squares having heights that are one step apart. In one direction, you can get a coloring from a height function by taking the heights mod 3. In the other direction, starting from a colored grid and a choice of the height of one of the squares (with the correct value modulo 3) you can go from there to adjacent squares step by step and figure out what their height has to be. It all works out so that, no matter how you do it, you always get a consistent height function from each 3-coloring. But the function depends on the starting height of the first square. If you add a multiple of 3 to this height, you translate the whole function up or down by that amount, and the translation turns out to be important.
So if you have two different local flat foldings of the Miura crease pattern, you can translate them in this way into two different 3-colorings, and two different height functions. Then you can convert one of the height functions into the other one, move by move, by repeatedly finding the square whose height is farthest away from its final value and shifting it two steps closer. The total number of steps equals half the volume of the three-dimensional space between the two height functions, and that’s the best you can do to get one height function to the other. But it might not be the best you can do to get one 3-coloring to the other, because of the choice of starting heights. To find the minimum number of moves to get from one local flat folding to another there’s one more computation that you have to do first: find two starting heights for the two height functions that makes the volume between them as small as possible.
For a bit more on height functions, 3-colorings, and the “arctic circle” that one gets by choosing 3-colorings of the square grid randomly, you can read the web page “random 3-coloring of the square and cubic lattice”, by Joakim Linde, describing his joint work with Cris Moore in this area.