Paper by Erik D. Demaine
- Reference:
- 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.
- Abstract:
-
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.
- 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.
These pages are generated automagically from a
BibTeX file.
Last updated July 23, 2024 by
Erik Demaine.