Paper by Erik D. Demaine

Hugo A. Akitaya, Erik D. Demaine, and Jason S. Ku, “Computing Flat-Folded States”, in Origami8: Proceedings of the 8th International Meeting on Origami in Science, Mathematics and Education (OSME 2024), Melbourne, Australia, July 16–18, 2024, to appear.

In this paper, we introduce a facewise definition for global flat foldability on crease patterns with n convex faces that constrains O(n3) 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{n2 p, n2 + m p2}) = O(n3) 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(n3 + ∑i = 1k ti3 2ti) time and O(∑i = 1k si) space, where ti and si parameterize a decomposition of the problem into k independent components. Lastly, we prove that unassigned crease patterns on n faces can have at most 2O(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.

The paper is 19 pages.

The paper is available in PDF (801k).
See information on file formats.
[Google Scholar search]

See also other papers by Erik Demaine.
These pages are generated automagically from a BibTeX file.
Last updated June 13, 2024 by Erik Demaine.