文献

J-GLOBAL ID：202102221410809249   整理番号：21A0548307

ボックスひだ状の折り目パターンを持つ2×n地図折畳みのための効率的アルゴリズム

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

著者 (3件)： Jia Yiyang (University of Tsukuba) ,  Mitani Jun (University of Tsukuba) ,  Uehara Ryuhei (School of Information Science, JAIST)
資料名： Journal of Information Processing (Web)  (Journal of Information Processing (Web))
巻： 28  ページ： 806-815(J-STAGE)  発行年： 2020年 
JST資料番号： U0109A  ISSN： 1882-6652  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： 本論文で,著者らは地図の折畳み問題の変化を研究した。入力は,サイズ2×nのボックスひだ状の折り目パターンを持つ2×n地図である。正確には,平面グラフとして折り目パターンを見ると,その頂点とエッジはそれぞれ正方形と対角格子の平面グラフの頂点セットとエッジセットのサブセットを形成する。問題は,地図を平らに折りたたむことができるかどうかである。答えが「はい」の場合,次に決定を下すための時間複雑さは何であるか?著者らの結論は,そのようなボックスひだ状の折り目パターンを持つ任意の局所的に平坦な折畳み2×n地図は,全体的に平に折畳むことができる,ということであった。著者らは平坦折畳み性を決定しそして実行可能な折畳み方法を見つけるための線形時間アルゴリズムを提示した。(翻訳著者抄録)

シソーラス用語： 型 ,  *地図 ,  *折畳み ,  *アルゴリズム ,  平面グラフ ,  頂点 ,  端部
準シソーラス用語： *パターン ,  ひだ状 ,  線形時間アルゴリズム

著者キーワード (3件)： 地図折畳み問題 ,  フラットフォールド ,  線形時間アルゴリズム

分類 (1件)： 計算理論  (JB02000A)

引用文献 (12件)：

• [1] Hull, T.: The combinatorics of flat folds: A survey, 3rd International Meeting of Origami Science, pp.29-38 (2002).
• [2] Bern, M. and Hayes, B.: The Complexity of Flat Origami, Ann. ACM-SIAM Symposium on Discrete Algorithms, pp.175-183, ACM (1996).
• [3] Kawasaki, T.: On the relation between mountain-creases and valley-creases on a flat origami, Proc. 2nd International Meeting of Origami Science and Scientific Origami, Huzita, H. (Ed.), Origami Science and Technology, pp.229-237 (1989).
• [4] Justin, J.: Towards a mathematical theory of origami, Miura, K. (Ed.), Proc. 2nd International Meeting of Origami Science and Scientific Origami, pp.15-29 (1997).
• [5] Kasahara, K. and Takahama, T.: Origami for the Connoisseur, Japan Publications Inc. (1998).

タイトルに関連する用語 (6件)： ボックス ,  ひだ ,  折り目 ,  地図 ,  折畳み ,  効率的アルゴリズム