Computing Flat-Folded States
摘要
In this paper, we introduce a facewise definition for global flat foldability on crease patterns with n convex faces that constrains \(O(n^3)\) conditions on the layer orders between pairs of overlapping faces, and prove that it is equivalent to the established pointwise definition. We use this formulation to show that (1) such a facewise layer order can be verified in \(O(\min \{n^2p, n^2 + mp^2\}) = O(n^3)\) time, where m and p parameterize the complexity of the folding and (2) all valid folded states of a crease pattern can be implicitly computed in \(O(n^3 + \sum _{i = 1}^k t_i^3 2^{t_i})\) time and \(O(\sum _{i=1}^k s_i)\) space, where \(t_i\) and \(s_i\) parameterize a decomposition of the problem into k independent components. Lastly, we prove that unassigned crease patterns on n faces can have at most \(2^{O(n^2)}\) folded states, while there exist assigned crease patterns on convex paper that achieve that bound, and assigned crease patterns on square paper that have \(2^{\Omega (n\log n)}\) folded states.