Paper by Erik D. Demaine

Reference:

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

Abstract:

In this paper, we introduce a facewise definition for global flat foldability on crease patterns with n convex faces that constrains O(n³) 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² p, n² + m p²}) = O(n³) 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³ + ∑_{i = 1}^k t_i³ 2^t_i) 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]