Folding a Paper Strip to Minimize Thickness
In this paper, we study how to fold a specified origami crease pattern in order to minimize the impact of paper thickness. Specifically, origami designs are often expressed by a mountain-valley pattern (plane graph of creases with relative fold orientations), but in general this specification is con...
| Main Authors: | , , , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer Nature America, Inc
2019
|
| Online Access: | https://hdl.handle.net/1721.1/121340 |
| _version_ | 1811082826452303872 |
|---|---|
| author | Demaine, Erik D Eppstein, David Hesterberg, Adam Ito, Hiro Lubiw, Anna Uehara, Ryuhei Uno, Yushi |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Demaine, Erik D Eppstein, David Hesterberg, Adam Ito, Hiro Lubiw, Anna Uehara, Ryuhei Uno, Yushi |
| author_sort | Demaine, Erik D |
| collection | MIT |
| description | In this paper, we study how to fold a specified origami crease pattern in order to minimize the impact of paper thickness. Specifically, origami designs are often expressed by a mountain-valley pattern (plane graph of creases with relative fold orientations), but in general this specification is consistent with exponentially many possible folded states. We analyze the complexity of finding the best consistent folded state according to twometrics:minimizing the total number of layers in the folded state (so that a “flat folding” is indeed close toflat), andminimizing the total amount of paper required to execute the folding (where “thicker” creases consume more paper). We prove both problems strongly NP-complete even for 1D folding. On the other hand, we prove the first problem fixed-parameter tractable in 1D with respect to the number of layers. |
| first_indexed | 2024-09-23T12:09:45Z |
| format | Article |
| id | mit-1721.1/121340 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T12:09:45Z |
| publishDate | 2019 |
| publisher | Springer Nature America, Inc |
| record_format | dspace |
| spelling | mit-1721.1/1213402022-09-28T00:35:51Z Folding a Paper Strip to Minimize Thickness Demaine, Erik D Eppstein, David Hesterberg, Adam Ito, Hiro Lubiw, Anna Uehara, Ryuhei Uno, Yushi Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Department of Mathematics In this paper, we study how to fold a specified origami crease pattern in order to minimize the impact of paper thickness. Specifically, origami designs are often expressed by a mountain-valley pattern (plane graph of creases with relative fold orientations), but in general this specification is consistent with exponentially many possible folded states. We analyze the complexity of finding the best consistent folded state according to twometrics:minimizing the total number of layers in the folded state (so that a “flat folding” is indeed close toflat), andminimizing the total amount of paper required to execute the folding (where “thicker” creases consume more paper). We prove both problems strongly NP-complete even for 1D folding. On the other hand, we prove the first problem fixed-parameter tractable in 1D with respect to the number of layers. National Science Foundation (U.S.). Origami Design for Integration of Self-assembling Systems for Engineering Innovation (grant EFRI- 124038) National Science Foundation (U.S.). Expedition grant (CCF-1138967) United States. Department of Defense. National Defense Science and Engineering Graduate (NDSEG) Fellowship (32 CFR 168a) 2019-06-18T14:27:21Z 2019-06-18T14:27:21Z 2016-01 2014-11 2019-06-18T12:34:28Z Article http://purl.org/eprint/type/ConferencePaper 1570-8667 https://hdl.handle.net/1721.1/121340 Demaine, Erik D., David Eppstein, Adam Hesterberg, Hiro Ito, Anna Lubiw, Ryuhei Uehara and Yushi Uno. "Folding a Paper Strip to Minimize Thickness." Journal of Discrete Algorithms 36: 18-26, 2016. en 10.1007/978-3-319-15612-5_11 Journal of Discrete Algorithms Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Springer Nature America, Inc arXiv |
| spellingShingle | Demaine, Erik D Eppstein, David Hesterberg, Adam Ito, Hiro Lubiw, Anna Uehara, Ryuhei Uno, Yushi Folding a Paper Strip to Minimize Thickness |
| title | Folding a Paper Strip to Minimize Thickness |
| title_full | Folding a Paper Strip to Minimize Thickness |
| title_fullStr | Folding a Paper Strip to Minimize Thickness |
| title_full_unstemmed | Folding a Paper Strip to Minimize Thickness |
| title_short | Folding a Paper Strip to Minimize Thickness |
| title_sort | folding a paper strip to minimize thickness |
| url | https://hdl.handle.net/1721.1/121340 |
| work_keys_str_mv | AT demaineerikd foldingapaperstriptominimizethickness AT eppsteindavid foldingapaperstriptominimizethickness AT hesterbergadam foldingapaperstriptominimizethickness AT itohiro foldingapaperstriptominimizethickness AT lubiwanna foldingapaperstriptominimizethickness AT uehararyuhei foldingapaperstriptominimizethickness AT unoyushi foldingapaperstriptominimizethickness |