Efficient Folding Algorithms for Regular Polyhedra
Efficient Folding Algorithms for Regular Polyhedra
复制标题
DOI：
--
复制
发表时间：
2021-05
期刊：
影响因子：
--
通讯作者：
Tonan Kamata;Akira Kadoguchi;T. Horiyama;Ryuhei Uehara
中科院分区：
文献类型：
--
作者：
Tonan Kamata;Akira Kadoguchi;T. Horiyama;Ryuhei Uehara
我们研究折叠问题，即对于给定的P和Q，一个多边形P是否可以折叠成一个多面体Q。最近，当Q是一个盒子时，已经开发了一个有效的算法来解决这个问题。我们将这个想法扩展到正多面体，也称为柏拉图体。我们的算法的基本思想是共同的，这就是所谓的冲压。然而，它们的计算复杂度取决于它们的几何性质。我们开发了四个算法的问题如下。(1)正四面体的一种算法，可推广到四面体。(2)一种求解正六面体（或立方体）的算法，它比以前已知的算法效率高得多。(3)一般三角面体的一种算法，它包含了Q是正八面体或正二十面体的情形。(4)正十二面体的一种算法。结合这些算法，我们可以得出结论，折叠问题可以解决伪多项式时间时，Q是一个正多面体和其他相关的固体。
We investigate the folding problem that asks if a polygon P can be folded to a polyhedron Q for given P and Q. Recently, an efficient algorithm for this problem has been developed when Q is a box. We extend this idea to regular polyhedra, also known as Platonic solids. The basic idea of our algorithms is common, which is called stamping. However, the computational complexities of them are different depending on their geometric properties. We developed four algorithms for the problem as follows. (1) An algorithm for a regular tetrahedron, which can be extended to a tetramonohedron. (2) An algorithm for a regular hexahedron (or a cube), which is much efficient than the previously known one. (3) An algorithm for a general deltahedron, which contains the cases that Q is a regular octahedron or a regular icosahedron. (4) An algorithm for a regular dodecahedron. Combining these algorithms, we can conclude that the folding problem can be solved pseudo-polynomial time when Q is a regular polyhedron and other related solid.