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.

BibTeX

@InProceedings{GraphFolding_SoCG2022,
  AUTHOR        = {Lily Chung and Erik D. Demaine and Della Hendrickson and Victor Luo},
  authororig    = {Lily Chung and Erik D. Demaine and Dylan Hendrickson and Victor Luo},
  TITLE         = {Flat Folding an Unassigned Single-Vertex Complex (Combinatorially Embedded Planar Graph with Specified Edge Lengths) without Flat Angles},
  BOOKTITLE     = {Proceedings of the 38th International Symposium on Computational Geometry (SoCG 2022)},
  bookurl       = {https://www.inf.fu-berlin.de/inst/ag-ti/socg22/socg.html},
  ADDRESS       = {Berlin, Germany},
  MONTH         = {June 7--10},
  YEAR          = 2022,
  PAGES         = {29:1--29:17},

  withstudent   = 1,
  doi           = {https://dx.doi.org/10.4230/LIPIcs.SoCG.2022.29},
  dblp          = {https://dblp.org/rec/conf/compgeom/ChungDHL22},
  comments      = {This paper is also available as <A HREF="https://arXiv.org/abs/2204.03696">arXiv:2204.03696</A>, and from <A HREF="https://doi.org/10.4230/LIPIcs.SoCG.2022.29">LIPIcs</A>.},
  updates       = {Our problem actually <i>cannot</i> be solved by existing weak embedding algorithms [4], because those algorithms do not preserve the combinatorial planar embedding. Thus our near-linear-time algorithm is in fact the first algorithm we know for this problem.},
}

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, and from LIPIcs.

Updates:

Our problem actually cannot be solved by existing weak embedding algorithms [4], because those algorithms do not preserve the combinatorial planar embedding. Thus our near-linear-time algorithm is in fact the first algorithm we know for this problem.

Availability:

The paper is available in PDF (1056k).

See information on file formats.

[Google Scholar search]