Efficient Algorithm for 2 × n Map Folding with a Box-pleated Crease Pattern

• Yiyang, Jia

• Jun, Mitani

• Ryuhei, Uehara

抄録

In this paper, we study a variation of the map folding problem. The input is a 2 × n map with a box-pleated crease pattern of size 2 × n. Precisely, viewing the crease pattern as a planar graph, its vertices and edges respectively form the subsets of the vertices set and edges set of the planar graph of the square and diagonal grid. The question is whether the map can be flat-folded or not. If the answer is yes, then what is the time complexity to make the decision? Our conclusion is that any locally flat-foldable 2 × n map with such a box-pleated crease pattern is globally flat-foldable. We present linear-time algorithms for both deciding the flat foldability and finding a feasible way of folding.------------------------------This is a preprint of an article intended for publication Journal ofInformation Processing(JIP). This preprint should not be cited. Thisarticle should be cited as: Journal of Information Processing Vol.28(2020) (online)DOI　http://dx.doi.org/10.2197/ipsjjip.28.806------------------------------

In this paper, we study a variation of the map folding problem. The input is a 2 × n map with a box-pleated crease pattern of size 2 × n. Precisely, viewing the crease pattern as a planar graph, its vertices and edges respectively form the subsets of the vertices set and edges set of the planar graph of the square and diagonal grid. The question is whether the map can be flat-folded or not. If the answer is yes, then what is the time complexity to make the decision? Our conclusion is that any locally flat-foldable 2 × n map with such a box-pleated crease pattern is globally flat-foldable. We present linear-time algorithms for both deciding the flat foldability and finding a feasible way of folding.------------------------------This is a preprint of an article intended for publication Journal ofInformation Processing(JIP). This preprint should not be cited. Thisarticle should be cited as: Journal of Information Processing Vol.28(2020) (online)DOI　http://dx.doi.org/10.2197/ipsjjip.28.806------------------------------

収録刊行物

• 情報処理学会論文誌

  情報処理学会論文誌 61 (12), 2020-12-15

キーワード

• [特集：離散と計算の幾何・グラフ・ゲーム] map folding problem, flat-foldable, linear-time algorithm

詳細情報

• CRID: 1050006297346642432
• NII論文ID: 170000184203
• NII書誌ID: AN00116647
• ISSN: 18827764
• Web Site: http://id.nii.ac.jp/1001/00208718/
• 本文言語コード: en
• 資料種別: journal article
• データソース種別:
  • IRDB
  • CiNii Articles