Paper by Erik D. Demaine

Reference:

Lily Chung, Erik D. Demaine, Della Hendrickson, and Victor Luo, “Flat Folding an Unassigned Single-Vertex Complex (Combinatorially Embedded Planar Graph with Specified Edge Lengths) without Flat Angles”, in Proceedings of the 38th International Symposium on Computational Geometry (SoCG 2022), Berlin, Germany, June 7–10, 2022, 29:1–29:17.

Abstract:

A foundational result in origami mathematics is Kawasaki and Justin's simple, efficient characterization of flat foldability for unassigned single-vertex crease patterns (where each crease can fold mountain or valley) on flat material. This result was later generalized to cones of material, where the angles glued at the single vertex may not sum to 360°. Here we generalize these results to when the material forms a complex (instead of a manifold), and thus the angles are glued at the single vertex in the structure of an arbitrary planar graph (instead of a cycle). Like the earlier characterizations, we require all creases to fold mountain or valley, not remain unfolded flat; otherwise, the problem is known to be NP-complete (weakly for flat material and strongly for complexes). Equivalently, we efficiently characterize which combinatorially embedded planar graphs with prescribed edge lengths can fold flat, when all angles must be mountain or valley (not unfolded flat). Our algorithm runs in O(n log³ n) time, improving on the previous best algorithm of O(n² log n).

Comments:

This paper is also available as arXiv:2204.03696.

Availability:

The paper is available in PDF (1056k).

See information on file formats.

[Google Scholar search]