Paper by Erik D. Demaine
- Hugo A. Akitaya, Cordelia Avery, Joseph Bergeron, Erik D. Demaine, Justin Kopinsky, and Jason S. Ku, “Infinite All-Layers Simple Foldability”, Graphs and Combinatorics, volume 36, 2020, pages 231–244.
We study the problem of deciding whether a crease pattern can be folded by
simple folds (folding along one line at a time) under the infinite
all-layers model introduced by [ADK17], in which each simple fold is
defined by an infinite line and must fold all layers of paper that intersect
this line. This model is motivated by folding in manufacturing such as
sheet-metal bending. We improve on [ABD+04] by giving a
deterministic O(n)-time algorithm to decide simple foldability
of 1D crease patterns in the all-layers model. Then we extend this 1D result
to 2D, showing that simple foldability in the infinite all-layers model can be
decided in linear time for both unassigned and assigned axis-aligned
orthogonal crease patterns on axis-aligned 2D orthogonal paper. On the other
hand, we show that simple foldability is strongly NP-complete if a subset of
the creases have a mountain–valley assignment, even for axis-aligned
- This paper is also available as arXiv:1901.08564 and from SpringerLink.
- The paper is available in PDF (544k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- InfiniteSimpleFolds_JCDCGGG2017 (Infinite All-Layers Simple Foldability)
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated September 2, 2021 by