| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2018-05-26 13:30 平行斜め山谷付き折り目による紙帯の平坦折り 伊藤大雄（電通大）・奈良知惠（明大）・白濱和泉（ecbeing）・○戸村瑞穂（電通大）  COMP2018-4 |
|
| 抄録 | （和） | 平坦折り可能性問題は折り紙数学の代表的な問題であり，それは有限平面よりなる紙とその上に書かれた折り線の集合が与えられたときに，各折り線に指定された山折りか谷折りかの指示通りにすべての折り線を同時に平坦に折ることができるかという問題で，NP完全であることが知られている．しかし多項式時間で解ける部分問題もいくつか知られており，その代表的なものとして，紙を長方形の帯に限定し，折り線を紙帯の長軸方向に対して垂直とした場合（一次元山谷付き平坦折り問題）には，線形時間アルゴリズムがArkinらによって与えられている．本研究では，紙帯上の折り線が長軸となす角度を（$¥pi/2$に限らず）任意の角度$¥theta$ですべて等しい（すなわち全ての折り線は平行）とした問題「平行斜め山谷付き平坦折り問題」を考えた．折り線の角度$¥theta$が$¥pi/2$でない場合の顕著な特徴として，二つの折り線の距離がある程度（紙帯の幅と$¥theta$で決まる定数）離れていると，折った紙帯がズレて互いに影響しなくなる．従ってこの場合には両者を分割して二つの問題を独立に解くことが出来る．我々は，一次元山谷付き平坦折り問題のアルゴリズムに上記の分割の操作を加えることで，任意の角度$¥theta$に対する平行斜め山谷付き平坦折り問題の線形時間アルゴリズムを与えた． |
| （英） | 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 $¥theta$, which is not limited to $¥pi/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 $¥theta$ is not equal to $¥pi/2$, if the distance between the two creases is apart in some value (a constant fixed by the width of the strip and $¥theta$), 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 $¥theta$ by applying the above separate operation to the algorithm of the one-dimensional flat folding problem with mountain-valley-assigned creases. | |
| キーワード | （和） | 折り紙 / 平坦折り / アルゴリズム / 計算量 / / / / |
| （英） | origami / flat folding / algorithms / computational complexity / / / / | |
| 文献情報 | 信学技報, vol. 118, no. 68, COMP2018-4, pp. 63-70, 2018年5月. | |
| 資料番号 | COMP2018-4 | |
| 発行日 | 2018-05-18 (COMP) | |
| ISSN | Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2018-4 |
|
| 研究会情報 | |
| 研究会 | COMP IPSJ-AL |
| 開催期間 | 2018-05-25 - 2018-05-26 |
| 開催地（和） | 名古屋工業大学 |
| 開催地（英） | Nagoya Institute of Technology |
| テーマ（和） | |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2018-05-COMP-AL |
| 本文の言語 | 日本語 |
| タイトル（和） | 平行斜め山谷付き折り目による紙帯の平坦折り |
| サブタイトル（和） | |
| タイトル（英） | Strip flat folding with parallel oblique mountain-valley-assigned creases |
| サブタイトル（英） | |
| キーワード(1)（和/英） | 折り紙 / origami |
| キーワード(2)（和/英） | 平坦折り / flat folding |
| キーワード(3)（和/英） | アルゴリズム / algorithms |
| キーワード(4)（和/英） | 計算量 / computational complexity |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 伊藤 大雄 / Hiro Ito / イトウ ヒロオ |
| 第1著者 所属（和/英） | 電気通信大学 (略称： 電通大) The University of Electro-Communications (略称： UEC) |
| 第2著者 氏名（和/英/ヨミ） | 奈良 知惠 / Chie Nara / ナラ チエ |
| 第2著者 所属（和/英） | 明治大学 (略称： 明大) Meiji University (略称： Meiji Univ.) |
| 第3著者 氏名（和/英/ヨミ） | 白濱 和泉 / Izumi Shirahama / シラハマ イズミ |
| 第3著者 所属（和/英） | ecbeing (略称： ecbeing) ECBEING (略称： ECBEING) |
| 第4著者 氏名（和/英/ヨミ） | 戸村 瑞穂 / Mizuho Tomura / トムラ ミズホ |
| 第4著者 所属（和/英） | 電気通信大学 (略称： 電通大) The University of Electro-Communications (略称： UEC) |
| 講演者 | 第4著者 |
| 発表日時 | 2018-05-26 13:30:00 |
| 発表時間 | 30分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2018-4 |
| 巻番号（vol） | vol.118 |
| 号番号（no） | no.68 |
| ページ範囲 | pp.63-70 |
| ページ数 | 8 |
| 発行日 | 2018-05-18 (COMP) |
[研究会発表申込システムのトップページに戻る]