Flattening single-vertex origami: the non-expansive case

ABSTRACT

A single-vertex origami is a piece of paper with straight-line rays called creases emanating from a fold vertex placed in its interior or on its boundary. The Single-Vertex Origami Problem asks whether it is always possible to reconfigure the creased paper from any configuration compatible with the metric, to a flat position, in such a way that the paper is not torn, stretched and, for rigid origami, not bent anywhere except along the given creases.

Streinu and Whiteley showed how to reduce the single-vertex origami problem to the Carpenter's Rule Problem for spherical polygons. Using spherical expansive motions, they solved the cases of open < π and closed ≤ 2 π spherical polygons. Here, we solve the case of open polygons with total length between [π, 2π), which requires non-expansive motions. Our motion planning algorithm works in a finite number of discrete steps, for which we give precise bounds depending on both the number of links and the angle deficit.

REFERENCES

• 1: Devin J. Balkcom and Matthew T. Mason. Introducing robotic origami folding. In IEEE Internat. Conf. on Robotics and Automation (ICRA), pages 3245--3250, April 2004.
• 2: R. Connelly , E. D. Demaine , G. Rote, Straightening polygonal arcs and convexifying polygonal cycles, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.432, November 12-14, 2000
• 3: Erik D. Demaine , Joseph O'Rourke, Geometric Folding Algorithms: Linkages, Origami, Polyhedra, Cambridge University Press, New York, NY, 2007
• 4: Thomas C Hull. Rigid origami web site, http://kahuna.merrimack.edu/thull/rigid/rigid.html,2003.
• 5: Hyun Jin In, Sundeep Kumar, Yang Shao-Horn, and George Barbastathis. Origami fabrication of nanostructured, three-dimensional devices: Electrochemical capacitors with carbon electrodes. Applied Physics Letters, 88(8):083104, 2006.
• 6: S. M. Jurga, C. H. Hidrovo, J. Niemczura, Henry I. Smith, and George Barbastathis. Nanostructured origami. In IEEE Nanotechnology 2003 Proceedings, nr. TR-4, December 2003.
• 7: Liang Lu and Srinivas Akella. Folding cartons with fixtures: A motion planning approach. IEEE Trans. on Robotics and Automation, 16(4):346--356, August 2000.
• 8: Gaiane Panina. Planar pseudo-triangulations, spherical pseudo-tilings and hyperbolic virtual polytopes. Technical Report arXiv:math:MG/0607171, July 2006.
• 9: Günter Rote, Francisco Santos, and Ileana Streinu. Pseudo-triangulations: a survey. In J. E. Goodman, J. Pach, and R.Pollack, editors, Surveys on Discrete and Computational Geometry -- Twenty Years later, Contemporary Mathematics, vol. 453, pages 343--410. American Mathematical Society, 2008. http://arxiv.org/abs/math/0612672.
• 10: Paul W. K. Rothemund. Folding DNA to create nanoscale shapes and patterns. Nature, 440(7082):297--302, 2006.
• 11: Harry A. Schmitt, Don E. Waagen, George Barbastathis, and Ileana Streinu. Computational origami for sensor configuration and control. In Conf. Record of 38th Asilomar Conf. on Signals, Systems and Computers, vol. 1, pages 811--815. IEEE, 2004.
• 12: Guang Song and Nancy M. Amato. A motion planning approach to folding: From paper craft to protein structure prediction. In Proc. IEEE Internat. Conference on Robotics and Automation (ICRA), vol. 1, pages 948--953. IEEE, 2001.
• 13: I. Streinu, A combinatorial approach to planar non-colliding robot arm motion planning, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.443, November 12-14, 2000
• 14: Ileana Streinu and Walter Whiteley. Single-vertex origami and spherical expansive motions. In J. Akiyama and M. Kano, eds., Proc. Japan Conf. Discrete and Computational Geometry (JCDCG 2004), Lecture Notes in Computer Science, vol. 3742, pages 161--173, Tokai University, Tokyo, 2005. Springer Verlag.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.m Miscellaneous

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

General Terms:
Algorithms, Theory

Keywords:
computational geometry, expansive motion, folding, origami, pseudo-triangulation, spherical geometry