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.

BibTeX

@InProceedings{FlatFolder_OSME2024,
  AUTHOR        = {Hugo A. Akitaya and Erik D. Demaine and Jason S. Ku},
  TITLE         = {Computing Flat-Folded States},
  BOOKTITLE     = {Origami$^8$: Proceedings of the 8th International Meeting on Origami in Science, Mathematics and Education (OSME 2024)},
  bookurl       = {http://www.impactengineering.org/8OSME/},
  ADDRESS       = {Melbourne, Australia},
  MONTH         = {July 16--18},
  YEAR          = 2024,
  PAGES         = {to appear},

  length        = {19 pages},
}

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]