**Reference**:- Hugo A. Akitaya, Erik D. Demaine, and Jason S. Ku, “Computing Flat-Folded States”, in
*Origami*, Melbourne, Australia, July 16–18, 2024, to appear.^{8}: Proceedings of the 8th International Meeting on Origami in Science, Mathematics and Education (OSME 2024) **Abstract**:-
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*^{2}*p*,*n*^{2}+*m**p*^{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}+ ∑_{i = 1}^{k}*t*_{i}^{3}2^{ti}) time and*O*(∑_{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(n2)}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^{Ω(n log n)}folded states. **Length**:- The paper is 19 pages.
**Availability**:- The paper is available in PDF (801k).
- See information on file formats.
- [Google Scholar search]

See also other papers by Erik Demaine.

Last updated July 23, 2024 by Erik Demaine.