Home Issues About JGAA Instructions for Authors
 
 
Special Issue on Selected Papers from the 13th International Conference and Workshops on Algorithms and Computation, WALCOM 2019
DOI: 10.7155/jgaa.00520
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.
Communicated by Krishnendu Mukhopadhyaya and Shin-ichi Nakano
article (PDF)
BibTeX