Special Issue on Selected Papers from the 13th International Conference and Workshops on Algorithms and Computation, WALCOM 2019
Efficient Algorithm for Box Folding
Koichi Mizunashi, Takashi Horiyama, and Ryuhei Uehara
Vol. 24, no. 2, pp. 89-103, 2020. Regular paper.
Abstract 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.
Submitted: April 2019.
Reviewed: July 2019.
Revised: August 2019.
Accepted: October 2019.
Final: January 2020.
Published: February 2020.
article (PDF)