Efficient Algorithm for Box Folding - Mizunashi, Koichi; Horiyama, Takashi; Uehara, Ryuhei (Journal of Graph Algorithms and Applications, 2020)
For a given polygon $P$ and a polyhedron $Q$, the folding problem asks if $Q$ can be obtained from $P$ by folding it.This simple problem is quite complicated, and there is no known efficient algorithm that solves this problem in general.In this paper, we focus on the case that $Q$ is a box, and the size of $Q$ is not given.That is, input of the box folding problem is a polygon $P$, and it asks if $P$ can fold to boxes of certain sizes.We note that there exist an infinite number of polygons $P$ that can fold into three boxes of different sizes.In this paper, we give a pseudo polynomial time algorithm that computes all possible ways of folding of $P$ to boxes.