Flat Folding Problem with Parallel Creases on an Axis-Convex Polygonal Piece of Paper

Deciding flat foldability of a rectangular piece of paper with a given mountain-valley pattern is known to be NP-complete. One special case known to be solvable in linear time is when the creases are parallel to each other and to one side of the rectangular piece of paper; this case reduces to a purely one-dimensional folding problem. A linear-time algorithm for this problem was given by Arkin et al. in 2004. Recently, this case was generalized to a parallelogram of paper: if the piece of paper is a parallelogram and creases are parallel to each other and to one side of the paper, then it can be solved in linear-time by a group of the authors of this paper (Demaine et al. 2020). In this paper, we try to extend the result to a more general shape of paper. A polygonal piece of paper with parallel creases is said to be axis-convex if any straight line parallel or perpendicular to the creases shares a continuous part (i.e., a straight line segment) with the polygon. We show that under the restriction of that all creases are parallel to each other, if the shape of the paper is any axis-convex polygon, the flat-foldability problem with mountain-valley assignment can be solved in linear-time. For obtaining the linear-time algorithm, we redefine the operation SEPARATE, which was presented in the algorithm for the parallelogram cases, under new conditions.