# A Comparison of Different Folding Models in Variations of the Map Folding Problem
## 6 Performances of Three Folding Models in Boundary VOP  
### General Folding Model in Boundary VOP  
The conditions of the general folding model are no stretching, no tearing, and no penetration. The first two are naturally respected as the map being folded to the shape of a single square. Thus, for any given order, no matter a total order or a partial order on the set of all the squares, we only have to check the no penetration condition. There is a basic fact that a pair of horizontal neighbor squares would never penetrate with a pair of vertical neighbor squares, as the three possible overlap states illustrated in Figure 6a.  
Figure 5: The partly folded states of (**a,b**) in Figure 3.  
Figure 6: (**a**) Three possible overlap states of a pair of horizontal neighbor squares and a pair of vertical neighbor squares. (**b**) The notations and the coordinate system of the map.  
Hence, we can consider two horizontal boundary sides and two vertical boundary sides separately. Because of the similarity, here, we only exemplify the computation on two horizontal boundary sides. The following narration follows the notations with the help of the coordinate system given in Figure 6b. \(s_{i,j}\) (\(0\leq i<m\), \(0\leq j<n\)) refers to the square whose lower-left vertex is located at \((i,j)\) before any fold. We further assume that the upfront side of \(s_{0,0}\) is fixed. In the final folded state, on the bottom row, the creases between \(s_{2i-1,0}\) and \(s_{2i,0}\) would align on the \(y\)-axis, the creases between \(s_{2i,0}\) and \(s_{2i+1,0}\) would align on the line \(x=1\). On the top row, when m is odd (even), the creases between \(s_{2i-1,\,m-1}\) and \(s_{2i,\,m-1}\) would align on the \(y\)-axis (\(x=1\)), the creases between \(s_{2i,\,m-1}\) and \(s_{2i+1,\,m-1}\) would align on the line \(x=1\) (\(y\)-axis).  
For every two neighbor square pairs \([s_{i-1,\,p},\,s_{i,\,p}]\) and \([s_{j-1,\,q},\,s_{j,\,q}]\) whose creases align on the same line segment when completely folded, whether they penetrate each other or not, should be checked. Any penetrating state can be described as a permutation of \((s_{i-1,\,p},\,s_{j-1,\,q},\,s_{i,\,p},\,s_{j,\,q})\). A similar property holds for the two vertical boundary sides. Checking the existence of such orders on four boundary sides totally costs \(\mathcal{O}(m+n)\) time applying the stack structure introduced in [15].  
Conversely, based on the assignment, there exists a relation \(<\) on the set of boundary squares, defined as: \(s_{c,d}<s_{a,b}\) if \(s_{c,\,d}\) is below \(s_{a,b}\) in the final state. It is clear that \(<\) is a strict partial order because it satisfies:  
**(irreflexivity)** there is no \(s_{a,b}<s_{a,b}\);  
**(asymmetry)** if \(s_{a,b}<s_{c,d}\), then there is no \(s_{c,d}<s_{a,b}\);  
**(transitivity)** if \(s_{a,b}<s_{c,d}\) and \(s_{c,d}<s_{e,f}\), then \(s_{a,b}<s_{e,f}\).  
The strict partial order \(<\) corresponds to a directed acyclic graph whose nodes are the boundary squares and edges are from \(s_{c,d}\) to \(s_{a,b}\) when \(s_{c,d}<s_{a,b}\). Whether the input order follows a directed acyclic graph or not can be checked by a traverse. To conclude, we have Theorem 3. The proof is omitted because it follows the above analysis. The entire check takes \(O(m+n)\) time.  
Theorem 3: An input boundary overlapping order is valid if and only if it satisfies the partial order \(<\) and includes no penetration. The decision on the validity can be given in \(O(m+n)\) time.