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 log3 n) time, improving on the
previous best algorithm of
O(n2 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]
See also other papers by Erik Demaine.
These pages are generated automagically from a
BibTeX file.
Last updated July 23, 2024 by
Erik Demaine.