Universal Hinge Patterns for Folding Strips Efficiently into Any Grid Polyhedron
© Springer International Publishing AG 2017. We present two universal hinge patterns that enable a strip of material to fold into any connected surface made up of unit squares on the 3D cube grid—for example, the surface of any polycube. The folding is efficient: for target surfaces topologically eq...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer Nature
2021
|
| Online Access: | https://hdl.handle.net/1721.1/137746 |
| _version_ | 1811083619335143424 |
|---|---|
| author | Benbernou, Nadia M. Demaine, Erik D. Demaine, Martin L. Lubiw, Anna |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Benbernou, Nadia M. Demaine, Erik D. Demaine, Martin L. Lubiw, Anna |
| author_sort | Benbernou, Nadia M. |
| collection | MIT |
| description | © Springer International Publishing AG 2017. We present two universal hinge patterns that enable a strip of material to fold into any connected surface made up of unit squares on the 3D cube grid—for example, the surface of any polycube. The folding is efficient: for target surfaces topologically equivalent to a sphere, the strip needs to have only twice the target surface area, and the folding stacks at most two layers of material anywhere. These geometric results offer a new way to build programmable matter that is substantially more efficient than what is possible with a square N × N sheet of material, which can fold into all polycubes only of surface area O(N) and may stack Θ(N2) layers at one point. We also show how our strip foldings can be executed by a rigid motion without collisions (albeit assuming zero thickness), which is not possible in general with 2D sheet folding. To achieve these results, we develop new approximation algorithms for milling the surface of a grid polyhedron, which simultaneously give a 2-approximation in tour length and an 8/3-approximation in the number of turns. Both length and turns consume area when folding a strip, so we build on past approximation algorithms for these two objectives from 2D milling. |
| first_indexed | 2024-09-23T12:35:57Z |
| format | Article |
| id | mit-1721.1/137746 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T12:35:57Z |
| publishDate | 2021 |
| publisher | Springer Nature |
| record_format | dspace |
| spelling | mit-1721.1/1377462022-09-28T08:56:22Z Universal Hinge Patterns for Folding Strips Efficiently into Any Grid Polyhedron Benbernou, Nadia M. Demaine, Erik D. Demaine, Martin L. Lubiw, Anna Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory © Springer International Publishing AG 2017. We present two universal hinge patterns that enable a strip of material to fold into any connected surface made up of unit squares on the 3D cube grid—for example, the surface of any polycube. The folding is efficient: for target surfaces topologically equivalent to a sphere, the strip needs to have only twice the target surface area, and the folding stacks at most two layers of material anywhere. These geometric results offer a new way to build programmable matter that is substantially more efficient than what is possible with a square N × N sheet of material, which can fold into all polycubes only of surface area O(N) and may stack Θ(N2) layers at one point. We also show how our strip foldings can be executed by a rigid motion without collisions (albeit assuming zero thickness), which is not possible in general with 2D sheet folding. To achieve these results, we develop new approximation algorithms for milling the surface of a grid polyhedron, which simultaneously give a 2-approximation in tour length and an 8/3-approximation in the number of turns. Both length and turns consume area when folding a strip, so we build on past approximation algorithms for these two objectives from 2D milling. 2021-11-08T18:03:27Z 2021-11-08T18:03:27Z 2017 2019-06-12T12:52:17Z Article http://purl.org/eprint/type/ConferencePaper 0302-9743 1611-3349 https://hdl.handle.net/1721.1/137746 Benbernou, Nadia M., Demaine, Erik D., Demaine, Martin L. and Lubiw, Anna. 2017. "Universal Hinge Patterns for Folding Strips Efficiently into Any Grid Polyhedron." en 10.1007/978-3-319-62127-2_10 Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Springer Nature arXiv |
| spellingShingle | Benbernou, Nadia M. Demaine, Erik D. Demaine, Martin L. Lubiw, Anna Universal Hinge Patterns for Folding Strips Efficiently into Any Grid Polyhedron |
| title | Universal Hinge Patterns for Folding Strips Efficiently into Any Grid Polyhedron |
| title_full | Universal Hinge Patterns for Folding Strips Efficiently into Any Grid Polyhedron |
| title_fullStr | Universal Hinge Patterns for Folding Strips Efficiently into Any Grid Polyhedron |
| title_full_unstemmed | Universal Hinge Patterns for Folding Strips Efficiently into Any Grid Polyhedron |
| title_short | Universal Hinge Patterns for Folding Strips Efficiently into Any Grid Polyhedron |
| title_sort | universal hinge patterns for folding strips efficiently into any grid polyhedron |
| url | https://hdl.handle.net/1721.1/137746 |
| work_keys_str_mv | AT benbernounadiam universalhingepatternsforfoldingstripsefficientlyintoanygridpolyhedron AT demaineerikd universalhingepatternsforfoldingstripsefficientlyintoanygridpolyhedron AT demainemartinl universalhingepatternsforfoldingstripsefficientlyintoanygridpolyhedron AT lubiwanna universalhingepatternsforfoldingstripsefficientlyintoanygridpolyhedron |