Minimum Forcing Sets for Miura Folding Patterns
Minimum Forcing Sets for Miura Folding Patterns
复制标题
Miura 折叠图案的最小力集
DOI：
10.1137/1.9781611973730.11
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Thomas C. Hull
中科院分区：
文献类型：
--
作者：
Brad Ballinger;Mirela Damian;D. Eppstein;Robin Y. Flatland;J. Ginepro;Thomas C. Hull
我们介绍了数学折纸中的强迫集的研究。折纸材料沿称为折痕的直线段沿着折叠平坦，每个折痕被指定为山或谷的折叠方向。一个子集$F$的折痕是强制的，如果全球折叠山/谷分配可以推导出从其限制$F$。在本文中，我们专注于一类特殊的折叠模式称为三浦织，它划分成全等平行四边形的平面使用水平线和锯齿垂直线。我们开发了有效的算法，用于构建一个最小的强制设置的三浦ori地图，并决定是否一组给定的折痕是强迫或不。我们还提供了严格的限制大小的强制设置，建立标准的山谷分配的三浦ori是一个需要最折痕的强制设置。此外，给定一个部分山/谷分配到一个子集的折痕的三浦-ori地图，我们确定是否分配域可以扩展到一个局部平坦的折叠模式的所有折痕。在我们的研究结果的核心是一个新的对应平面折叠Miura ori地图和$3$-着色的网格图。
We introduce the study of forcing sets in mathematical origami. The origami material folds flat along straight line segments called creases, each of which is assigned a folding direction of mountain or valley. A subset $F$ of creases is forcing if the global folding mountain/valley assignment can be deduced from its restriction to $F$. In this paper we focus on one particular class of foldable patterns called Miura-ori, which divide the plane into congruent parallelograms using horizontal lines and zig-zag vertical lines. We develop efficient algorithms for constructing a minimum forcing set of a Miura-ori map, and for deciding whether a given set of creases is forcing or not. We also provide tight bounds on the size of a forcing set, establishing that the standard mountain-valley assignment for the Miura-ori is the one that requires the most creases in its forcing sets. Additionally, given a partial mountain/valley assignment to a subset of creases of a Miura-ori map, we determine whether the assignment domain can be extended to a locally flat-foldable pattern on all the creases. At the heart of our results is a novel correspondence between flat-foldable Miura-ori maps and $3$-colorings of grid graphs.