Efficient Enumeration of Flat-Foldable Single Vertex Crease Patterns

We investigate the following computational origami problem; the input is a positive integer n. We then draw n lines in a radial pattern. They are incident to the central point of a sheet of paper, and every angle between two consecutive lines is equal to 2π/n. Each line is assigned one of “mountain,” “valley,” and “flat” (or consequently unfolded), and only flat-foldable patterns will be output. We consider two crease patterns are the same if they can be equal with rotations and reflections. We propose an efficient enumeration algorithm for flat-foldable single vertex crease patterns for given n. In computational origami, there are well-known theorems for flat-foldability; Kawasaki Theorem and Maekawa Theorem. However, they give us necessary conditions, and sufficient condition is not known. Therefore, we have to enumerate and check flat-foldability one by one using the other algorithm. In this paper, we develop the first algorithm for the above stated problem by combining these results in nontrivial way, and show its analysis of efficiency.11th International Conference and Workshops, WALCOM 2017, Hsinchu, Taiwan, March 29–31, 2017, Proceeding