For Full-Text PDF, please login, if you are a member of IEICE, or go to Pay Per View on menu list, if you are a nonmember of IEICE.
 Efficient Enumeration of Flat-Foldable Single Vertex Crease PatternsKoji OUCHI  Ryuhei UEHARA  Publication IEICE TRANSACTIONS on Information and Systems   Vol.E102-D   No.3   pp.416-422Publication Date: 2019/03/01 Online ISSN: 1745-1361 DOI: 10.1587/transinf.2018FCP0004 Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science — Algorithm, Theory of Computation, and their Applications —)Category: Keyword: computational origami,  enumeration algorithm,  flat foldability,  Kawasaki theorem,  Maekawa theorem,  Full Text: PDF(528.9KB)>>Buy this Article Summary:  We investigate enumeration of distinct flat-foldable crease patterns under the following assumptions: positive integer n is given; every pattern is composed of n lines incident to the center of a sheet of paper; every angle between adjacent lines is equal to 2π/n; every line is assigned one of “mountain,” “valley,” and “flat (or consequently unfolded)”; crease patterns are considered to be equivalent if they are equal up to rotation and reflection. In this natural problem, we can use two well-known theorems for flat-foldability: the Kawasaki Theorem and the Maekawa Theorem in computational origami. Unfortunately, however, they are not enough to characterize all flat-foldable crease patterns. Therefore, so far, we have to enumerate and check flat-foldability one by one using computer. In this study, we develop the first algorithm for the above stated problem by combining these results in a nontrivial way and show its analysis of efficiency.