Efficient Algorithm for 2 × <i>n</i> Map Folding with a Box-pleated Crease Pattern

• Jia Yiyang

  University of Tsukuba

• Mitani Jun

  University of Tsukuba

• Uehara Ryuhei

  School of Information Science, JAIST

Abstract

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.

Journal

• Journal of Information Processing

  Journal of Information Processing 28 (0), 806-815, 2020

  Information Processing Society of Japan

Keywords

• map folding problem
• flat-foldable
• linear-time algorithm

Details

• CRID: 1390005506383177216
• NII Article ID: 130007956330
• DOI: 10.2197/ipsjjip.28.806
• ISSN: 18826652
• Web Site: https://www.jstage.jst.go.jp/article/ipsjjip/28/0/28_806/_pdf
• Text Lang: en
• Data Source:
  • JaLC
  • Crossref
  • CiNii Articles
  • KAKEN
• Abstract License Flag: Disallowed