Lang’s universal molecule algorithm. (English) Zbl 1330.68297

Summary: Robert Lang’s Universal Molecule algorithm, a landmark in modern computational origami, is the main component of his widely used TreeMaker program for origami design. It computes a crease pattern of a convex polygonal region, starting with a compatible metric tree. Although it has been informally described in several publications, neither the full power nor the inherent limitations of the method are well understood. In this paper we introduce a rigorous mathematical formalism to relate the input metric tree, the output crease pattern and the folded uniaxial origami base produced by the Universal Molecule algorithm. We characterize the family of tree-like 3D shapes that are foldable from the computed crease patterns and give a correctness proof of the algorithm.


68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
52B70 Polyhedral manifolds


Full Text: DOI


[1] Aichholzer, O; Alberts, D; Aurenhammer, F; Gärtner, B, A novel type of skeleton for polygons, Journal of Universal Computer Science, 1, 752-761, (1995) · Zbl 0943.68171
[2] Bowers, J.C., Lang’s universal molecule, I. Streinu.: algorithm. In: Proceedings of the Twenty-eighth Annual Symposium on Computational Geometry, SoCG ’12, pp. 419-420. ACM, New York (2012) · Zbl 1230.51023
[3] Bowers, J.C., Streinu, I.: Rigidity of origami universal molecules. In: Ida, T., Fleuriot, J. D. (eds.) Automated Deduction in Geometry, vol. 7993 of Lecture Notes in Computer Science, pp. 120-142. Springer (2012) · Zbl 1397.68198
[4] Bowers, J.C., Streinu, I.: Computing origami universal molecules with cyclic tournament forests. In: Proceedings of the 15th Intern. Symp. on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC’13), pages 42-52. IEEE (2013)
[5] Demaine, E.D., Demaine, M.L.: Computing extreme origami bases. Technical Report CS-97-22, Department of Computer Science, University of Waterloo (1997) · Zbl 0943.68171
[6] Demaine, E.D., Fekete, S.P., Lang, R.J.: Circle packing for origami design is hard. In: Wang-Iverson, P., Lang, R. J., Yim, M. (eds.) Origami 5: Fifth International Meeting of Origami Science, Mathematics, and Education, pp. 609-626. Taylor and Francis (2011)
[7] Demaine, E.D., O’Rourke, J.: Geometric Folding Algorithms: Linkages, Origami, and Polyhedra. Cambridge University Press (2007) · Zbl 1135.52009
[8] Huzita, H.: Proceedings First Intern. Meeting of Origami Science and Technology (1989), 143-158 (1991)
[9] Ida, T; Takahashi, H; Marin, M; Ghourabi, F; Kasem, A; Iglesias, A (ed.); Takayama, N (ed.), Computational construction of a maximum equilateral triangle inscribed in an origami, 361-372, (2006), Berlin Heidelberg · Zbl 1230.51023
[10] Ida, T; Tepeneu, D; Buchberger, B; Robu, J; Buchberger, B (ed.); Campbell, J (ed.), Proving and constraint solving in computational origami, 132-142, (2004), Berlin Heidelberg · Zbl 1109.68604
[11] Lang, R.J.: A computational algorithm for origami design. In: Proceedings of the 12th Annual ACM Symposium on Computational Geometry, pp. 98-105 (1996)
[12] Lang, R.J.: Treemaker 4.0: A program for origami design, http://www.langorigami.com (1998) · Zbl 1207.52021
[13] Lang, R.J.: Origami design secrets: mathematical methods for an ancient art. Ak Peters Series. A.K. Peters (2003) · Zbl 1032.00004
[14] Lang, R.J. (ed.): Origami 4: Fourth International Meeting of Origami Science, Mathematics, and Education. A. K. Peters (2009) · Zbl 1181.00030
[15] Lang, R.J., Demaine, E.D.: Facet ordering and crease assignment in uniaxial bases. In [14] (2009) · Zbl 1109.68604
[16] Panina, G; Streinu, I, Flattening single-vertex origami: the non-expansive case, Computational Geometry: Theory and Applications, 46, 678-687, (2010) · Zbl 1207.52021
[17] Streinu, I; Whiteley, W; Akiyama, J (ed.); Kano, M (ed.), Single-vertex origami and spherical expansive motions, (2005), Tokyo · Zbl 1136.52312
[18] Tachi, T, Origamizing polyhedral surfaces, Visualization and Computer Graphics, IEEE Transactions on, 16, 298-311, (2010)
[19] Wang-Iverson, P., Lang, R.J., Yim, M.: Origami 5: Fifth International Meeting of Origami Science, Mathematics, and Education. Taylor and Francis (2011) · Zbl 1235.00051
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.