Flat-Foldability for 1 × n Maps with Square/Diagonal Grid Patterns

摘要

In this paper, we propose three conclusions for 1 × n maps with square/diagonal grid patterns. First, for a 1 × n map consisting of all the vertical creases and all the diagonal creases as well as a mountain-valley assignment, if it obeys the local flat-foldability, then it can always be globally flat-folded and one of its flat-folded state can be reached in O(n) time. Second, for a 1 × n map consisting of only square/diagonal grid pattern, it also can always be globally flat-folded and one of its flat-foldable state can be reached in O(n) time. We give theoretical proofs for both of them and propose corresponding algorithms. Then, we prove the NP-hardness of the problem of determining the global flat-foldability for a 1 × n map consisting of a square/diagonal grid pattern and a specific mountain-valley assignment. Also, we show that given an order of the faces for an m × n map with all the vertical creases and all the diagonal creases assigned to be mountains or valleys, we can determine its validity in O(mn) time.