平行斜め山谷付き折り目による紙帯の平坦折り

• Item type: SIG Technical Reports(1)
• 公開日: 2018-05-18
• タイトル: 平行斜め山谷付き折り目による紙帯の平坦折り
• タイトル / 言語: en
• タイトル: Strip flat folding with parallel oblique mountain-valley-assigned creases
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 電気通信大学情報理工学研究科
• 著者所属: 明治大学先端数理科学インステイテユート
• 著者所属: 株式会社ecbein
• 著者所属: 電気通信大学情報理工学研究科
• 著者所属(英): en
• 著者所属(英): School of Informatics and Engineering, The University of Electro-Communications
• 著者所属(英): en
• 著者所属(英): Institute of Advanced Study of Mathematical Sciences, Meiji University
• 著者所属(英): en
• 著者所属(英): ECBEING CORP.
• 著者所属(英): en
• 著者所属(英): School of Informatics and Engineering, The University of Electro-Communication
• 著者名: 伊藤, 大雄; 奈良, 知惠; 白濱, 和泉; 戸村, 瑞穂
• 著者名(英): Hiro, Ito; Chie, Nara; Izumi, Shirahama; Mizuho, Tomura
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 平坦折り可能性問題は折り紙数学の代表的な問題であり，それは有限平面よりなる紙とその上に書かれた折り線の集合が与えられたときに，各折り線に指定された山折りか谷折りかの指示通りにすべての折り線を同時に平坦に折ることができるかという問題で，NP 完全であることが知られている．しかし多項式時間で解ける部分問題もいくつか知られており，その代表的なものとして，紙を長方形の帯に限定し，折り線を紙帯の長軸方向に対して垂直とした場合 （一次元山谷付き平坦折り問題） には，線形時間アルゴリズムが Arkin らによって与えられている．本研究では，紙帯上の折り線が長軸となす角度を （π/2 に限らず）任意の角度 θ ですべて等しい （すなわち全ての折り線は平行） とした問題 「平行斜め山谷付き平坦折り問題」 を考えた．折り線の角度 θ が π/2 でない場合の顕著な特徴として，二つの折り線の距離がある程度 （紙帯の幅と θ で決まる定数） 離れていると，折った紙帯がズレて互いに影響しなくなる．従ってこの場合には両者を分割して二つの問題を独立に解くことが出来る．我々は，一次元山谷付き平坦折り問題のアルゴリズムに上記の分割の操作を加えることで，任意の角度 θ に対する平行斜め山谷付き平坦折り問題の線形時間アルゴリズムを与えた．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: The flat foldability problem is a typical problem of origami mathematics, which asks whether or not a given paper with creases each of which has a mountain-valley assignment is flat foldable. This problem is know to be in NP-complete. However, some subproblems that can be solved in polynomial time have been known, and a representative example is that the paper is limited to a rectangular strip and the creases are perpendicular to the long axis of the strip, which is called one-dimensional flat folding problem with mountain-valley-assigned creases, and a linear time algorithm was given by Arkin et al. In this study, we tried to solve a problem that the angle formed by creases is equal to an arbitrary angle θ, which is not limited to π/2, i.e., all creases are parallel. We call this problem strip flat folding problem with parallel oblique mountain-valley-assigned creases. As a remarkable feature when θ is not equal to π/2, if the distance between the two creases is apart in some value (a constant fixed by the width of the strip and θ), the strip can be separated into two, since they never affect each other. Therefore, in this case, we can solve the two problems independently. We present a linear-time algorithm for the strip flat folding problem with parallel oblique mountain-valley-assigned creases with an arbitrary angle θ by applying the above separate operation to the algorithm of the one-dimensional flat folding problem with mountain-valley-assigned creases.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2018-AL-168, 号 10, p. 1-8, 発行日 2018-05-18
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8566
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会