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.
|
Journal Supporters
|