Infinite All-Layers Simple Foldability
Abstract 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 Akitaya et al. (J Inform Process 25:582–589, 2017), in which each simple fold is defined by an infinite...
| Main Authors: | , , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer Japan
2021
|
| Online Access: | https://hdl.handle.net/1721.1/131401 |
| _version_ | 1811076696504270848 |
|---|---|
| author | Akitaya, Hugo A Avery, Cordelia Bergeron, Joseph Demaine, Erik D Kopinsky, Justin Ku, Jason S |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Akitaya, Hugo A Avery, Cordelia Bergeron, Joseph Demaine, Erik D Kopinsky, Justin Ku, Jason S |
| author_sort | Akitaya, Hugo A |
| collection | MIT |
| description | Abstract
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 Akitaya et al. (J Inform Process 25:582–589, 2017), 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 Arkin et al. (Comput Geom Theory Appl 29(1):23–46, 2014) 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 rectangular paper. |
| first_indexed | 2024-09-23T10:26:06Z |
| format | Article |
| id | mit-1721.1/131401 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T10:26:06Z |
| publishDate | 2021 |
| publisher | Springer Japan |
| record_format | dspace |
| spelling | mit-1721.1/1314012023-03-01T15:56:40Z Infinite All-Layers Simple Foldability Akitaya, Hugo A Avery, Cordelia Bergeron, Joseph Demaine, Erik D Kopinsky, Justin Ku, Jason S Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Abstract 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 Akitaya et al. (J Inform Process 25:582–589, 2017), 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 Arkin et al. (Comput Geom Theory Appl 29(1):23–46, 2014) 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 rectangular paper. 2021-09-20T17:16:55Z 2021-09-20T17:16:55Z 2019-10-16 2020-09-24T20:44:02Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/131401 en https://doi.org/10.1007/s00373-019-02079-2 Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ Springer Japan KK, part of Springer Nature application/pdf Springer Japan Springer Japan |
| spellingShingle | Akitaya, Hugo A Avery, Cordelia Bergeron, Joseph Demaine, Erik D Kopinsky, Justin Ku, Jason S Infinite All-Layers Simple Foldability |
| title | Infinite All-Layers Simple Foldability |
| title_full | Infinite All-Layers Simple Foldability |
| title_fullStr | Infinite All-Layers Simple Foldability |
| title_full_unstemmed | Infinite All-Layers Simple Foldability |
| title_short | Infinite All-Layers Simple Foldability |
| title_sort | infinite all layers simple foldability |
| url | https://hdl.handle.net/1721.1/131401 |
| work_keys_str_mv | AT akitayahugoa infinitealllayerssimplefoldability AT averycordelia infinitealllayerssimplefoldability AT bergeronjoseph infinitealllayerssimplefoldability AT demaineerikd infinitealllayerssimplefoldability AT kopinskyjustin infinitealllayerssimplefoldability AT kujasons infinitealllayerssimplefoldability |