# A Comparison of Different Folding Models in Variations of the Map Folding Problem
## 4 Simple Folding Model in 1D VOP  
It has been proven in [5] that both the final flat-folded state and every partly flat-folded state of the general folding model can be reached through a sequence of simple folds and unfolds. In this section, we will prove that although there exist partly flat-folded states of the general folding model unreachable for the simple folding model, their sets of reachable final flat-folded states are always the same. With the simple folding model, once two layers are folded to touch each other, they would not be separated apart again. This is the difference between the simple folding model and the simple folding-unfolding model on the reachable (partly) folded states. Because of this property, not all the partly flat-folded states of the simple folding-unfolding model can be reached by the simple folding model. An example is given in Figure 3. The red part in Figure 3b is the main reason for the unreachability. The details will be given in the following explanation. However, in the final folded state, all the layers would be aligned over a \(1\times 1\) area (represented by a line segment with 1 in length). In the following, we will show that the folds applied on such red parts can be applied earlier to avoid the simple unfolds. In other words, for any final folded state, we can always find a corresponding simple folding sequence, where every step causes some layers to touch each other. We use the same simple folding operation, crimps, and end-folds as [13] to indicate our folding process but neglect the creases remaining unfolded at every step. The two partly folded states after folding a crimp and after folding an end-fold are described in Figure 2b. The size of the map before the fold is assumed to be \(1\times n\) with its left end located on \(x=0\). We denote the coordinates of points \(A\) to \(G\) as \(x_{A}\) to \(x_{G}\), which are all integers. Then, we have \(x_{B}-x_{A}>x_{C}-x_{B}<x_{D}-x_{C}\) for the crimp and \(n-x_{G}\leq x_{G}-x_{F}\) for the end-fold. The two states are respectively described by the following formulas, where \(o(x)\) indicates the squares folded to the coordinate \(x\), \(s_{i}\) (\(0\leq i\leq n\)) indicates the squares whose lower-left vertex is located at point \(i\) before any fold, and tuples indicate the order of the squares from bottom to top. For the crimp, we have:  
\[o(x)=\left\{ \begin{array}{cc}s_{x},&x\ <\ 2x_{B}\ -\ x_{C}\\ \left(s_{x},s_{2x_{B}-x-1},\ s_{x+2x_{C}-2x_{B}}\right),&2x_{B}\ -\ x_{C}\leq\ x\ <\ x_{B}\\ s_{x+2x_{C}-x_{B}},&x_{B}\ \leq\ x\ <\ 2x_{B}+n-2x_{C}\end{array} \right. \tag{1}\]  
Figure 3: A \(1\times 20\) map comprising five segments from \(l_{1}\) to \(l_{5}\) aligning in order. Two input overlapping orders correspond to the states **(a,b)**. **(a)** is reachable by the simple folding model while **(b)** is not. and for the end-fold, we have  
\[o(x)=\left\{ \begin{array}{cc}s_{x},&x<2x_{G}-n\\ \left(s_{x},s_{2x_{G}-x-1}\right),&2x_{G}-n\leq\ x<x_{G}\end{array} \right. \tag{2}\]  
The MV assignment of the map is uniquely determined by the input overlapping order, as described in [15]. The assignment can be computed in time linear to \(n\). To make the latter computing easier, we first utilize their approach to determine the MV assignment. **Step 1**. Compute the MV assignment of the map. Then, repeat the following three steps until either the map is shrunk to size \(1\times 1\) or the input order is determined to be unreachable. In the former case, the complete simple folding sequence could also be obtained. **Step 2**. Find out the neighbor segments which are adjacent in the overlapping order. Decide the crease between them to be the first crease to fold. If no such neighbor segment exists, the input overlapping order is unreachable. **Step 3**. According to the creases decided in Step 2, decide the crimps and end-folds on the 1D map by referring to Formulas (1) and (2). If no feasible crimp or end-fold exists, the input order is unreachable. **Step 4**.