# A Comparison of Different Folding Models in Variations of the Map Folding Problem
## 1 Introduction  
Problems in the field of origami are becoming more and more popular because of their applicability in robotics and computational modeling, especially the origamis whose crease patterns (comprising all the folding line segments and their intersections) are relatively simple. Some examples of how they have been applied in robotics manufacturing and moving paths are proposed in [1; 2; 3; 4]. In this paper, we mainly focus on the origamis with grid patterns as their crease patterns, which are called _map folding_. We investigate different variations of map folding problems with three folding models. These models are the _general folding_, the _simple folding_, and the _simple folding-unfolding_. The general folding is an abstract of manual works, while the latter two are abstracts of the folding patterns which robots can manage. By comparing the performance of these folding models in different folding problems, our conclusion provides an important reference for applying these folding models to robotics manufacturing and computational modeling. To introduce the topic of this research, we present the terminologies at first. Precisely, an \(m\times n\) map is a rectangle sheet with m rows and n columns composed of \(m\times n\) congruent squares. When m equals 1, the map reduces to one dimension and is usually represented by a line segment with segments in unit length representing squares of the map. The edges of the squares not located at the boundary of the map are called _creases_. They together comprise a _grid pattern_ as the _crease pattern_ of the map. Two squares sharing the same crease are called a pair of _neighbor_ squares. A _complete folding sequence_ of the map indicates the sequence of folds that fold the map to the shape of a unit square on the plane. Every single square becomes a unique layer in the folded state. In any partly or completely flat-folded state, we say a pair of squares whose surfaces touch each other are _adjacent_. Theoverlapping orders refer to the orders given onto the set of all the squares of the map (total orders) or a subset consisting of only the squares aligning on the boundary of the map (_boundary orders_, illustrated as the shadowed squares in Figure 1a. If such an input order corresponds to the order of these squares aligning from bottom to top in a practical folded state of the map, then it is said to be _valid_. In this paper, the capability of three folding models: the _general folding_, the _(some-layers) simple folding_, and the _(some-layers) simple folding-unfolding_, are compared in three variations of the map folding problem, which are referred to as _valid overlapping order problems_ in this paper: _valid total overlapping order problem_ of \(1\times n\)_maps_, _valid total overlapping order problem of \(m\times n\)_maps_, and _valid boundary overlapping order problem of \(m\times n\)_maps_. For conciseness, in the following, these valid overlapping order problems are referred to as _1D VOP_, _Total VOP_, and _Boundary VOP_, respectively. Their corresponding decision problems concern the decisions on the validity of input overlapping orders. The general folding model uses general folds with only the practical restrictions of the paper itself, namely, no tearing, stretching, or penetrating (self-intersection). Instead, the simple folding model uses only simple folds while the simple folding-unfolding model comprises both simple folds and its reverses operation, simple unfolds. Both simple folds and unfolds are always applied simultaneously on some top or bottom layers along a single line (crease line) and satisfying that the next state is also flat, as illustrated in Figure 1b. Every simple fold and unfold can be indicated by a set of creases lines. We will show that although the three folding models have the same reachability of the overlapping order in 1D VOP, their reachable valid overlapping orders in both Total VOP and Boundary VOP are in strict inclusion relations.