Document Open Access Logo

Flat Folding an Unassigned Single-Vertex Complex (Combinatorially Embedded Planar Graph with Specified Edge Lengths) Without Flat Angles

Authors Lily Chung , Erik D. Demaine , Dylan Hendrickson , Victor Luo

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2022.29.pdf
  • Filesize: 1.15 MB
  • 17 pages

Document Identifiers

Author Details

Lily Chung
  • Massachusetts Institute of Technology, Cambridge, MA, USA
Erik D. Demaine
  • Massachusetts Institute of Technology, Cambridge, MA, USA
Dylan Hendrickson
  • Massachusetts Institute of Technology, Cambridge, MA, USA
Victor Luo
  • Massachusetts Institute of Technology, Cambridge, MA, USA

Acknowledgements

We thank Joseph O'Rourke and the anonymous referees for helpful suggestions. This work grew out of an open problem session and a final project from the MIT class on Geometric Folding Algorithms: Linkages, Origami, Polyhedra (6.849) held Fall 2020.

Cite AsGet BibTex

Lily Chung, Erik D. Demaine, Dylan Hendrickson, and Victor Luo. Flat Folding an Unassigned Single-Vertex Complex (Combinatorially Embedded Planar Graph with Specified Edge Lengths) Without Flat Angles. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 29:1-29:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.SoCG.2022.29

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).

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • Graph drawing
  • folding
  • origami
  • polyhedral complex
  • algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Timothy G. Abbott, Erik D. Demaine, and Blaise Gassend. A generalized carpenter’s rule theorem for self-touching linkages. arXiv:0901.1322, 2009. URL: http://arxiv.org/abs/0901.1322.
  2. Zachary Abel, Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Jayson Lynch, Tao B. Schardl, and Isaac Shapiro-Ellowitz. Folding equilateral plane graphs. International Journal of Computational Geometry and Applications, 23(2):75-92, April 2013. Google Scholar
  3. Zachary Abel, Erik D. Demaine, Martin L. Demaine, David Eppstein, Anna Lubiw, and Ryuhei Uehara. Flat foldings of plane graphs with prescribed angles and edge lengths. Journal of Computational Geometry, 9(1):74-93, 2018. Google Scholar
  4. Hugo A. Akitaya, Radoslav Fulek, and Csaba D. Tóth. Recognizing weak embeddings of graphs. ACM Transactions on Algorithms, 15(4), October 2019. URL: https://doi.org/10.1145/3344549.
  5. Marshall Bern and Barry Hayes. The complexity of flat origami. In Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 175-183, Atlanta, January 1996. Google Scholar
  6. Paola Bertolazzi, Giuseppe Di Battista, Giuseppe Liotta, and Carlo Mannino. Upward drawings of triconnected digraphs. Algorithmica, 12(6):476-497, 1994. Google Scholar
  7. Glencora Borradaile, Philip N. Klein, Shay Mozes, Yahav Nussbaum, and Christian Wulff-Nilsen. Multiple-source multiple-sink maximum flow in directed planar graphs in near-linear time. SIAM Journal on Computing, 46(4):1280-1303, 2017. URL: https://doi.org/10.1137/15M1042929.
  8. M. Chlebík and J. Chlebíková. Approximation hardness of dominating set problems in bounded degree graphs. Information and Computation, 206(11):1264-1275, 2008. URL: https://doi.org/10.1016/j.ic.2008.07.003.
  9. Robert Connelly, Erik D. Demaine, and Günter Rote. Infinitesimally locked self-touching linkages with applications to locked trees. In J. Calvo, K. Millett, and E. Rawdon, editors, Physical Knots: Knotting, Linking, and Folding of Geometric Objects in 3-space, pages 287-311. American Mathematical Society, 2002. Google Scholar
  10. Erik D. Demaine. 6.849: Geometric folding algorithms: Linkages, origami, polyhedra: Lecture 5. MIT class, fall 2010. URL: https://courses.csail.mit.edu/6.849/fall10/lectures/L05.html?notes=4.
  11. Erik D. Demaine and Joseph O'Rourke. Geometric Folding Algorithms: Linkages, Origami, Polyhedra. Cambridge University Press, 2007. Google Scholar
  12. Ivan Tadeu Ferreira Antunes Filho. Characterizing boolean satisfiability variants. M.eng. thesis, Massachusetts Institute of Technology, 2019. URL: https://erikdemaine.org/theses/ifilho.pdf.
  13. Thomas Hull. On the mathematics of flat origamis. Congressus Numerantium, 100:215-224, 1994. Google Scholar
  14. Thomas Hull. The combinatorics of flat folds: a survey. In Origami³: Proceedings of the 3rd International Meeting of Origami Science, Math, and Education, pages 29-38, Monterey, California, March 2001. Google Scholar
  15. Thomas C. Hull. Origametry: Mathematical Methods in Paper Folding. Cambridge University Press, December 2020. Google Scholar
  16. Jacques Justin. Aspects mathematiques du pliage de papier (Mathematical aspects of paper folding). In H. Huzita, editor, Proceedings of the 1st International Meeting of Origami Science and Technology, pages 263-277, Ferrara, Italy, December 1989. Originally appeared in L'Ouvert, number 47, 1987, pages 1-14. URL: https://publimath.univ-irem.fr/biblio/IST87008.htm.
  17. Toshikazu Kawasaki. On the relation between mountain-creases and valley-creases of a flat origami. In H. Huzita, editor, Proceedings of the 1st International Meeting of Origami Science and Technology, pages 229-237, Ferrara, Italy, December 1989. An unabridged Japanese version appeared in Sasebo College of Technology Report, 27:153-157, 1990. Google Scholar
  18. Wolfgang Mulzer and Günter Rote. Minimum-weight triangulation is NP-hard. Journal of the ACM, 55(2), May 2008. URL: https://doi.org/10.1145/1346330.1346336.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact