Infinite All-Layers Simple Foldability
Infinite All-Layers Simple Foldability
复制标题
无限的全层简单折叠性
DOI：
10.1007/s00373-019-02079-2
复制
发表时间：
2019
影响因子：
0.7
通讯作者：
Jason S. Ku
中科院分区：
文献类型：
--
作者：
H. Akitaya;C. Avery;Joseph Bergeron;E. Demaine;Justin Kopinsky;Jason S. Ku
我们研究了在 Akitaya 等人引入的无限全层模型下确定折痕图案是否可以通过简单折叠（一次沿一条线折叠）来折叠的问题。 (J Inform Process 25:582–589, 2017)，其中每个简单折叠都由一条无限线定义，并且必须折叠与该线相交的所有纸张层。该模型的灵感来自制造过程中的折叠，例如钣金弯曲。我们改进了 Arkin 等人。 （Comput Geom Theory Appl 29(1):23–46, 2014）通过给出确定性的 O(n) 时间算法来确定全层模型中一维折痕图案的简单可折叠性。然后，我们将此 1D 结果扩展到 2D，表明对于轴对齐 2D 正交纸张上未分配和分配的轴对齐正交折痕图案，可以在线性时间内确定无限全层模型中的简单可折叠性。另一方面，我们表明，如果折痕的子集具有山谷分配，则简单的可折叠性是强 NP 完全的，即使对于轴对齐的矩形纸张也是如此。
We study the problem of deciding whether a crease pattern can be folded by simple folds (folding along one line at a time) under theinfinite all-layersmodel introduced by Akitaya et al. (J Inform Process 25:582–589, 2017), in which each simple fold is defined by an infinite line and must fold all layers of paper that intersect this line. This model is motivated by folding in manufacturing such as sheet-metal bending. We improve on Arkin et al. (Comput Geom Theory Appl 29(1):23–46, 2014) by giving a deterministicO(n)-time algorithm to decide simple foldability of 1D crease patterns in the all-layers model. Then we extend this 1D result to 2D, showing that simple foldability in the infinite all-layers model can be decided in linear time for both unassigned and assigned axis-aligned orthogonal crease patterns on axis-aligned 2D orthogonal paper. On the other hand, we show that simple foldability is strongly NP-complete if a subset of the creases have a mountain–valley assignment, even for axis-aligned rectangular paper.