Geometric Folding Algorithms:
Linkages, Origami, Polyhedra

The book contains many open problems (see the Index under Open Problems, p. 468). Inevitably, some will be resolved as time passes and before we can release a Second Edition. Here we will maintain a list of those Open Problems in the book which either have been closed, or on which there has been reportable progress of which investigators should be aware.

• Open Problem 18.1: Continuous Flattening (p. 279): Can every flat folded state of a polyhedron be reached by continuous flattening.

  The important special case of convex polyhedra has been solved by Jin-ichi Itoh, Chie Nara, and Costin Vilcu in [7]: every convex polyhedron may be continuously flattened, in many different ways.

• Open Problem 23.1: D-forms and Pita-Forms (p. 354): Might a D-form (or a pita-form) have a crease?

  This problem was settled in a recent paper [4] that shows that D-forms have no creases but pita-forms may have one crease. A new open problem here is to determine whether or not a pita form might have no crease, as all examples have one.

• Open Problem 23.2: Practical Algorithm for Cauchy Rigidity (p. 357): Find a practical algorithm for constructing the unique polyhedron guaranteed by Cauchy's Theorem.

  In a break-through paper [1], Bobenko and Izmestiev defined a procedure that can reconstruct a convex polyhedron from its faces by numerically solving a differential equation. And indeed they implemented it and the software is publically available. For a high-level description of the Bobenko-Izmestiev algorithm, see [3]. Their original algorithm had no bound, but recently Kane et al. [2] showed that it can be implemented to run in pseudopolynomial time.

• Prismatoid Unfolding (p. 380): "It is natural to hope that the top and bottom faces ... can be affixed to opposite sides of the band, resulting in a nonverlapping edge unfolding of a prismatoid."

  This hope was shown to be in vain via a counterexample in [9]: for every band unfolding of the example, every top & bottom placement results in overlap.

• Open Problem 25.1: Folding Polygons to (Nonconvex) Polyhedra (p. 384): Does every polygon fold to some simple polyhedron?

  We just recently realized that this problem is solved (positively) by a theorem of Burago and Zalgaller [5] from more than a decade earlier. See the note [6] that explains how their theorem solves it (it requires some translation between different mathematical languages).

• Open Problem 25.5: Flat Foldings (p. 423): Characterize those polygons that have a flat folding

  This is only a small advance on the general problem, but [8]

  describes an O(n³) algorithm to determine whether a particular Alexandrov gluing of a polygon of n vertices results in a flat folding, that is, a doubly covered convex polygon. The open problem essentially asks whether a flat polyhedron could result from any folding, whereas this algorithm just detects that for a particular folding.

1. Alexander I. Bobenko and Ivan Izmestiev. "Alexandrov’s theorem, weighted Delaunay triangulations, and mixed volumes," Annales de l'institut Fourier, 58 No. 2 (2008), p. 447-505.
2. Daniel Kane, Gregory N. Price, Erik D. Demaine, "A Pseudopolynomial Algorithm for Alexandrov's Theorem," arXiv:0812.5030v1 [cs.CG], 2008.
3. Joseph O'Rourke, "Computational Geometry Column 49," SIGACT News, Vol. 38, No. 2, Issue 143, June 2007, pp. 55-59.
4. Gregory N. Price and Erik D. Demaine, "Generalized D-forms have no spurious creases, Discrete & Comptutational Geometry, 43(1) 179-186.
5. Yu. D. Burago and V. A. Zalgaller. "Isometric piecewise linear immersions of two-dimensional manifolds with polyhedral metrics into R³." St. Petersburg Math. J., 7(3):369--385, 1996.
6. J. O'Rourke, "On Folding a Polygon to a Polyhedron," arXiv:1007.3181v1 [cs.CG], July 2010.
7. Jin-ichi Itoh, Chie Nara, Costin Vilcu, "Continuous flattening of convex polyhedra," XIV Spanish Meeting on Computational Geometry, 2011, Centre de Recerca Matematica Documents Vol. 8, pp. 95-98.
8. J. O'Rourke, "On Flat Polyhedra deriving from Alexandrov's Theorem," 1007.2016v1 [cs.CG], July 2010.
9. J. O'Rourke, "Band Unfoldings and Prismatoids: A Counterexample." Smith Computer Science Technical Report 087, Oct. 2007. arXiv:0710.0811v2 [cs.CG].