**Reference**:- Nadia M. Benbernou, Erik D. Demaine, Martin L. Demaine, and Anna Lubiw, “Universal Hinge Patterns for Folding Strips Efficiently into Any Grid Polyhedron”, in
*Proceedings of the 16th International Symposium on Algorithms and Data Structures (WADS 2017)*, July 31–August 2, 2017, to appear. **Abstract**:-
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 Θ(*N*^{2}) 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.

**Length**:- The paper is 12 pages.
**Availability**:- The paper is available in PDF (2682k).
- See information on file formats.
- [Google Scholar search]
**Related webpages**:- Strip Folding Font

See also other papers by Erik Demaine.

Last updated October 16, 2017 by Erik Demaine.