Eﬃcient Algorithms for Folding Problem of Regular Polyhedra
Ryuhei UEHARA, JAIST, Japan (uehara@jaist.ac.jp)
vature 180◦ , which consists of three equilateral triangles. Therefore, this algorithm cannot deal with aregular tetrahedron. On the other hand, it can deal
with a vertex of curvature 360◦ , where six equilateraltriangles make a ﬂat hexagonal face. That is, we allow each face to consist of coplanar regular triangles,
or each face can be any convex polyiamond. Thus
there are an inﬁnite of non-strictly convex deltahedra that our algorithm can deal with. In summary, if
Q has a non-strictly convex deltahedra with no vertex of curvature 180◦ , our algorithm solves the folding
problem in pseudo-polynomial time.

We investigate the folding problem when both apolygon and a polyhedron are explicitly given; for agiven polygon P and a polyhedron Q, it asks if P canfold to Q or not. This is a natural problem, however,there are few results so far. When Q is a regular tetrahedron, we have a mathematical characterization ofits net [1]; according to this result, P can fold to Q ifand only if P is a kind of tiling. The folding problem
has been investigated when Q is a box. Some special
cases were investigated [4, 7] and it is solved in thegeneral case [6].
We show that the folding problem can be solved
eﬃciently for a regular polyhedron (a. k. a. Platonicsolid). aka While there are ﬁve Platonic solids, ourmain result consists of four algorithms. That is, weinvestigate four problems depending on the target
solid, and show pseudo-polynomial time algorithmsfor them.
The ﬁrst algorithm solves the folding problem for aregular tetrahedron. We give a bit stronger algorithm
that solves the folding problem for a tetramonohedron, which is a tetrahedron consists of four congruent acute triangles. As already mentioned, a mathematical characterization of a net of a regular tetrahedron and its extension to a tetramonohedron is also
given by Akiyama and Nara [1, 3]. (The details canbe found in a book [2, Chapter 3]). However, as far
as the authors know, any algorithm for checking thesecharacterizations has never been given explicitly (wethank an anonymous referee of [5], who mentioned
this point). We give a pseudo-polynomial time algorithm for the folding problem for a tetramonohedron.
The next algorithm solves the folding problem for aregular cube. As mentioned above, there is a known
algorithm for this problem [6]. We improve this running time from O(D7 n2 (D5 +log n)) time to O(D2 n3 )time.
The third algorithm solves the folding problem fora regular dodecahedron. The last algorithm solves
the folding problem for a set of special convex deltahedra. Usually, a deltahedron means a polyhedron
whose faces are congruent equilateral triangles. In
our algorithm, it cannot deal with a vertex of cur-References[1] Akiyama, J.: Tile-Makers and Semi-Tile-Makers.
The Mathematical Association of America Monthly
114, 602–609 (2007)[2] Akiyama, J., Matsunaga, K.: Treks into Intuitive
Geometry. Springer (2015)[3] Akiyama, J., Nara, C.: Developments of Polyhedra Using Oblique Coordinates.
J. Indonesia. Math. Soc. 13(1), 99–114 (2007)[4] Horiyama, T., Mizunashi, K.: Folding Orthogonal
Polygons into Rectangular Boxes. In: In Proc. of19th Japan-Korea Joint Workshop on Algorithms
and Computation (WAAC 2016) (2016)[5] Kamata, T., Kadoguchi, A., Horiyama, T., Uehara,
R.: Eﬃcient Folding Algorithms for Regular Polyhedra. In: 32nd Canadian Conference on Computational Geometry (CCCG 2020), pp. 131–137 (2020)[6] Mizunashi, K., Horiyama, T., Uehara, R.: Eﬃcient
Algorithm for Box Folding. Journal of Graph Algorithms and Applications 24(2), 89–103 (2020)[7] Xu, D., Horiyama, T., Shirakawa, T., Uehara,R.: Common Developments of Three Incongruent Boxes of Area 30. Computational Geometry: Theory and Applications 64, 1–17 (2017).
DOI:10.1016/j.comgeo.2017.03.001

1