@article{Akitaya_Brunner_Demaine_Hendrickson_Luo_Tockman_2023, title={Complexity of Simple Folding of Mixed Orthogonal Crease Patterns: Discrete and Computational Geometry, Graphs, and Games}, volume={21}, url={https://thaijmath2.in.cmu.ac.th/index.php/thaijmath/article/view/1563}, abstractNote={<p>Continuing results from JCDCGGG 2016 and 2017, we solve several new cases of the simple foldability problem -- deciding which crease patterns can be folded flat by a sequence of (some model of) simple folds. We give new efficient algorithms for mixed crease patterns, where some creases are assigned mountain/valley while others are unassigned,&nbsp;for all 1D cases and for 2D rectangular paper with orthogonal one-layer simple folds. By contrast, we show strong NP-completeness for mixed orthogonal crease patterns&nbsp;on 2D rectangular paper with some-layers simple folds, complementing a previous result for all-layers simple folds.&nbsp;We also prove strong NP-completeness for finite simple folds&nbsp;(no matter the number of layers) of unassigned orthogonal crease patterns on arbitrary paper, complementing a previous result for assigned crease patterns, and contrasting with a previous positive result for infinite all-layers simple folds.&nbsp;In total, we obtain a characterization of polynomial vs.\ NP-hard for all cases -- finite/infinite one/some/all-layers simple folds of&nbsp;assigned/unassigned/mixed orthogonal crease patterns on&nbsp;1D/rectangular/arbitrary paper -- except the unsolved case of infinite all-layers simple folds of assigned orthogonal crease patterns on arbitrary paper.</p>}, number={4}, journal={Thai Journal of Mathematics}, author={Akitaya, Hugo and Brunner, Josh and Demaine, Erik D. and Hendrickson, Dylan and Luo, Victor and Tockman, Andy}, year={2023}, month={Dec.}, pages={1025–1046} }