Geometric Folding Algorithms:
|
by Erik D. Demaine and Joseph O'Rourke |
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.
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.
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.
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.
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.
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).
This is only a small advance on the general problem, but [8] describes an O(n3) 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.