文献

J-GLOBAL ID：202102266688566798   整理番号：21A0548308

地図を単純に折畳む時の層の有効な順序付け

Valid Orderings of Layers When Simple-Folding a Map

著者 (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  ページ： 816-824(J-STAGE)  発行年： 2020年 
JST資料番号： U0109A  ISSN： 1882-6652  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： 本研究で,著者らはm×n地図の正方形全ての重なる順序が,単純な折畳みと呼ばれる特定の文脈下で有効かどうかに関する決定問題を検討した。この問題は,地図折畳みの分野に属した。それは,単純な折畳みの文脈下で1×n地図の有効な順序の決定問題と,一般的折畳みの文脈下でのm×n地図の有効な順序の決定問題,両方の変化であった。著者らは,正方形間の隣接関係を表す有向グラフの構築に基づいて,この問題を解くための方法とその対応する線形時間アルゴリズムを提供した。(翻訳著者抄録)

シソーラス用語： *地図 ,  *折畳み ,  順序 ,  アルゴリズム ,  正方形 ,  決定問題 ,  性質 ,  有向グラフ ,  紙
準シソーラス用語： *順序づけ ,  折り紙 ,  線形時間アルゴリズム ,  隣接関係

著者キーワード (4件)： 地図折畳み問題 ,  重複順序 ,  m nマップ ,  線形時間アルゴリズム

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

引用文献 (10件)：

• [1] 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).
• [2] 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).
• [3] Kasahara, K. and Takahama, T.: Origami for the Connoisseur, Japan Publications Inc. (1998).
• [4] Bern, M. and Hayes, B.: The Complexity of Flat Origami, Ann. ACM-SIAM Symposium on Discrete Algorithms, pp.175-183, ACM (1996).
• [5] Arkin, E.M., Bender, M.A., Demaine, E.D., Demaine, M.L., Mitchell, J.S., Sethia, S. and Skiena, S.S.: When Can You Fold a Map, Computational Geometry: Theory and Applications, Vol.29, No.1, pp.23-46 (2002).

タイトルに関連する用語 (3件)： 地図 ,  層 ,  順序付け