Box Pleating is Hard
Box Pleating is Hard
复制标题
箱形褶皱很硬
DOI：
10.1007/978-3-319-48532-4_15
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
R. Uehara
中科院分区：
文献类型：
--
作者：
H. Akitaya;K. C. Cheung;E. D. Demaine;T. Horiyama;T. Hull;J. S. Ku;T. Tachi;R. Uehara
一般折痕图案的平折性在二十多年前就被认为是困难的。在本文中，我们证明了决定平面折叠仍然是NP完全的，即使是盒打褶，折痕形成一个子集的正方形网格与对角线。此外，我们提供了新的术语来隐式地表示平面折叠的全局层顺序，并提出了一个新的平面简化框架网格对齐的小工具。
Flat foldability of general crease patterns was first claimed to be hard for over twenty years. In this paper we prove that deciding flat foldability remains NP-complete even for box pleating, where creases form a subset of a square grid with diagonals. In addition, we provide new terminology to implicitly represent the global layer order of a flat folding, and present a new planar reduction framework for grid-aligned gadgets.