The complexity of the stamp folding problem

详细信息    查看全文

• 作者：Takuya Umesato ; Toshiki Saitoh ; Ryuhei Uehara ; Hiro Ito ; Yoshio Okamoto
• 关键词：Linkage ; NP-complete ; Optimization problem ; Pleat folding ; Rigid origami
• 刊名：Theoretical Computer Science
• 出版年：2013
• 出版时间：29 July, 2013
• 年：2013
• 卷：497
• 期：Complete
• 页码：13-19
• 全文大小：466 K

文摘

There are many folded states consistent with a given mountain-valley pattern of equidistant creases on a long paper strip. We would like to fold a paper strip such that the number of paper layers between each pair of hinged paper segments, called the crease width at the crease point, is minimized. This problem is called the stamp folding problem and there are two variants of this problem: minimization of the maximum crease width, and minimization of the total crease width. This optimization problem was recently introduced and investigated from the viewpoint of the counting problem. However, its computational complexity is not known. In this paper, we first show that the minimization problem of the maximum crease width is strongly NP-complete. Hence we cannot solve the problem in polynomial time unless P=NP. We next propose an algorithm that solves the minimization problem. The algorithm itself is a straightforward one, but its analysis is not trivial. We show that this algorithm runs in time where is the number of creases and is the total crease width.