Simple Folding is Really Hard

• Item type: Journal(1)
• 公開日: 2017-08-15
• タイトル: Simple Folding is Really Hard
• タイトル / 言語: en
• タイトル: Simple Folding is Really Hard
• 言語: eng
• キーワード / 主題Scheme: Other
• キーワード / 主題: [特集：離散と計算の幾何・グラフ・ゲーム] computational geometry, computational origami, simple folds, strong NP-completeness
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: Tufts University
• 著者所属: MIT Computer Science and Artificial Intelligence Laboratory
• 著者所属: MIT Computer Science and Artificial Intelligence Laboratory
• 著者所属(英): en
• 著者所属(英): Tufts University
• 著者所属(英): en
• 著者所属(英): MIT Computer Science and Artificial Intelligence Laboratory
• 著者所属(英): en
• 著者所属(英): MIT Computer Science and Artificial Intelligence Laboratory
• 著者名: Hugo, A. Akitaya; Erik, D. Demaine; Jason, S. Ku
• 著者名(英): Hugo, A. Akitaya; Erik, D. Demaine; Jason, S. Ku
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: Simple folding (folding along one line at a time) is a practical form of origami used in manufacturing such as sheet metal bending. We prove strong NP-completeness of deciding whether a crease pattern can be simply folded, both for orthogonal paper with assigned orthogonal creases and for square paper with assigned or unassigned creases at multiples of 45°. These results settle a long standing open problem, where weak NP-hardness was established for a subset of the models considered here, leaving open the possibility of pseudopolynomial-time algorithms. We also formalize and generalize the previously proposed simple folding models, and introduce new infinite simple-fold models motivated by practical manufacturing. In the infinite models, we extend our strong NP-hardness results, as well as polynomial-time algorithms for rectangular paper with assigned or unassigned orthogonal creases (map folding). These results motivate why rectangular maps have orthogonal but not diagonal creases.; ------------------------------; This is a preprint of an article intended for publication Journal of; Information Processing(JIP). This preprint should not be cited. This; article should be cited as: Journal of Information Processing Vol.25(2017) (online); DOI http://dx.doi.org/10.2197/ipsjjip.25.580; ------------------------------
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Simple folding (folding along one line at a time) is a practical form of origami used in manufacturing such as sheet metal bending. We prove strong NP-completeness of deciding whether a crease pattern can be simply folded, both for orthogonal paper with assigned orthogonal creases and for square paper with assigned or unassigned creases at multiples of 45°. These results settle a long standing open problem, where weak NP-hardness was established for a subset of the models considered here, leaving open the possibility of pseudopolynomial-time algorithms. We also formalize and generalize the previously proposed simple folding models, and introduce new infinite simple-fold models motivated by practical manufacturing. In the infinite models, we extend our strong NP-hardness results, as well as polynomial-time algorithms for rectangular paper with assigned or unassigned orthogonal creases (map folding). These results motivate why rectangular maps have orthogonal but not diagonal creases.; ------------------------------; This is a preprint of an article intended for publication Journal of; Information Processing(JIP). This preprint should not be cited. This; article should be cited as: Journal of Information Processing Vol.25(2017) (online); DOI http://dx.doi.org/10.2197/ipsjjip.25.580; ------------------------------
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 58, 号 8, 発行日 2017-08-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764