# A Comparison of Different Folding Models in Variations of the Map Folding Problem
## 2 Preliminaries and Terminology  
Map folding concerns the flat folding of special grid patterns. More precisely, the original map folding problem proposed by [PERSON] in 1997 asks the computational complexity when deciding the flat-foldability of a regular grid pattern of size \(m\times n\) with a _Mountain-Valley assignment (MV assignment)_. An MV assignment is a constraint description over the folding direction of every crease as either a mountain (\"M\", denoted by the red solid-line segments) or a valley (\"V\", denoted by a blue dashed-line segment). As a problem actually not as trivial as it intuitively seems, it remains unsolved for almost 40 years until today. A simple pattern which is locally flat-foldable at every vertex (which means, every small neighborhood of its vertices is foldable) but not globally flat-foldable is illustrated in Figure 2a to exemplify this point. For general patterns, the existence of a flat-folded state and the existence of general folding progress leading to the state is proven to be equivalent [7]. Thus, the flat-foldability, i.e., whether a given crease pattern (with or without a Mountain-Valley assignment) can be flat-folded or not, can be decided through a check on the existence of a valid overlapping of all the faces, which is proven to be NP-hard generally [8]. Although the flat-foldability is globally intractable, locally, the flat-foldability around every single vertex in a small neighborhood involving no other vertex can be decided in linear time by checking some restrictions [9]. Two well-known restrictions for both MV-assigned or unassigned cases were presented as the Kawasaki-Justin Theorem, and the Maekawa-Justin Theorem [10; 11; 12]. [PERSON] et al. first proposed the simple folding model to simplify the map folding problem [13]. Three kinds of simple-folding models, _one-layer simple folding_, _all-layers simple folding_, and _some-layers simple folding_, are considered in their study. Among them, the some-layers simple folding model is the most general model, and we follow it in this paper. As introduced above, every _simple fold_ transforms some top or bottom layers along a single line to achieve a state also flat. One-layer simple folding model and all-layers simple folding models specify the number of folded layers to one and the number of all the layers, respectively. In their research, they used two kinds of special simple folds, _crimps_, and _end-folds_, as the basic operations. In a 1D map, as illustrated in Figure 2b, an _end-fold_ is a fold at either the first or the last crease point. The interval between the last crease (which becomes a point since the map is illustrated as a line segment) and its corresponding end of the map is no longer than its neighbor interval. A _crimp_ is a fold along a pair of adjacent crease points labeled \"_MV_\" or \"_VM_\". The length of the interval between the two crease points is a local minimum. They have probed several kinds of maps, including _one-dimensional maps_ with every unit generalized to arbitrary length, _regular maps_ as grid patterns of size \(m\times n\), and some extended patterns only keeping the orthogonality of the creases. Considering the relationship with this research, we introduce their main results for the first two kinds of maps. They proposed linear-time algorithms to decide the flat-foldability of input MV-assigned 1D maps using one-layer simple folds and some-layer simple folds, as well as a  
Figure 2: (a) A 2 \(\times\) 5 map which cannot be flat-folded; (b) An example of the crimp and the end-fold. polynomial-time algorithm for the same problem with all-layers simple folds. All of the results mentioned above were introduced in [13]. Later, [PERSON] et al. presented some NP-hard results of these simple folding models for orthogonal patterns, with fixed unit lengths, either with or without MV-assignments [14]. The some-layers simple folding model was further extended by [PERSON] into the _some-layers simple folding-unfolding model_.