Folding a paper strip to minimize thickness
Folding a paper strip to minimize thickness
复制标题
DOI：
10.1016/j.jda.2015.09.003
复制
发表时间：
2014-11
期刊：
影响因子：
--
通讯作者：
E. Demaine;D. Eppstein;Adam Hesterberg;Hiro Ito;A. Lubiw;Ryuhei Uehara;Yushi Uno
中科院分区：
文献类型：
--
作者：
E. Demaine;D. Eppstein;Adam Hesterberg;Hiro Ito;A. Lubiw;Ryuhei Uehara;Yushi Uno
在本文中，我们研究如何折叠一个指定的折纸折痕模式，以尽量减少纸张厚度的影响。具体地说，折纸设计通常由山谷图案（具有相对折叠方向的折痕的平面图）表示，但一般来说，本说明书与指数地许多可能的折叠状态一致。我们根据两个指标来分析找到最佳一致折叠状态的复杂性：最小化折叠状态下的总层数（因此“平面折叠”确实接近平面），以及最小化执行折叠所需的纸张总量（其中“较厚”折痕消耗更多纸张）。我们证明了这两个问题强NP-完全，即使是一维折叠。另一方面，我们证明了第一个问题的固定参数听话的一维相对于层数。
In this paper, we study how to fold a specified origami crease pattern in order to minimize the impact of paper thickness. Specifically, origami designs are often expressed by a mountain-valley pattern (plane graph of creases with relative fold orientations), but in general this specification is consistent with exponentially many possible folded states. We analyze the complexity of finding the best consistent folded state according to two metrics: minimizing the total number of layers in the folded state (so that a “flat folding” is indeed close to flat), and minimizing the total amount of paper required to execute the folding (where “thicker” creases consume more paper). We prove both problems strongly NP-complete even for 1D folding. On the other hand, we prove the first problem fixed-parameter tractable in 1D with respect to the number of layers.