文献

J-GLOBAL ID：202102279227507594   整理番号：21A0548309

山-谷の割当てを有する平行または非鋭角のジグザグ折り目を持つストリップの平坦折畳み

Flat Folding a Strip with Parallel or Nonacute Zigzag Creases with Mountain-Valley Assignment

著者 (7件)： Demaine Erik D. (Massachusetts Institute of Technology) ,  Demaine Martin L. (Massachusetts Institute of Technology) ,  Ito Hiro (The University of Electro-Communications) ,  Nara Chie (Meiji University) ,  Shirahama Izumi (ECBEING CORP.) ,  Tachi Tomohiro (The University of Tokyo) ,  Tomura Mizuho (The University of Electro-Communications)
資料名： Journal of Information Processing (Web)  (Journal of Information Processing (Web))
巻： 28  ページ： 825-833(J-STAGE)  発行年： 2020年 
JST資料番号： U0109A  ISSN： 1882-6652  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： 与えられた山-谷のパターンの平坦折畳みを決定することは,NP完全であることが知られている。線形時間で解けることが知られている1つの特殊なケースは,折り目が互いに平行でそして紙の長方形片の2つの側面に垂直な場合で,この事例は純粋に1次元折畳みの問題になる。本論文で,著者らは2つのより一般的な特殊な事例,(1)すべての折り目が互いにかつ紙の平行四辺形の2つの側面に平行であるが,おそらくは平行四辺形の他の2つの側面に斜めである,そして(2)折り目は正規のジグザグを形成し,その2つの方向(紙片の2つの側面に斜めに傾斜する,ジグとザグ)は互いに非鋭角を形成する,で平坦折畳みのための線形時間アルゴリズムを提供した。後者のジグザグ事例で,著者らは,各折り目パターンを山,谷,または非折畳みとして指定した場合でも,各折り目パターンを平らに折畳むことができることを実際に証明した。(翻訳著者抄録)

シソーラス用語： *折れ線 ,  *折畳み ,  *帯板 ,  紙 ,  アルゴリズム ,  型 ,  NP完全問題 ,  長方形 ,  一次元 ,  四角形
準シソーラス用語： NP完全 ,  パターン ,  *折り紙 ,  線形時間アルゴリズム ,  平行四辺形

著者キーワード (4件)： 折り紙 ,  しわパターン ,  フラットフォールディング ,  アルゴリズム

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

引用文献 (11件)：

• [1] Akitaya, H., Avery, C., Bergeron, J., Demaine, E.D., Kopinsky, J. and Ku, J.: Infinite All-Layers Simple Foldability, Graphs and Combinatorics, Vol.36, pp.231-244 (2020).
• [2] Akitaya, H.A., Cheung, K.C., Demaine, E.D., Horiyama, T., Hull, T.C., Ku, J.S., Tachi, T. and Uehara, R.: Box pleating is hard, Revised Papers from the 18th Japan Conference on Discrete and Computational Geometry and Graphs (JCDCGG 2015), Lecture Notes in Computer Science, Vol.9943, pp.167-179 (2015).
• [3] Arkin, E.M., Bender, M.A., Demaine, E.D., Demaine, M.L., Mitchell, J.S.B., Sethia, S. and Skiena, S.S.: When Can You Fold a Map?, Computational Geometry: Theory and Applications, Vol.29, No.1, pp.23-46 (2004).
• [4] Bern, M. and Hayes, B.: The Complexity of Flat Origami, Proc. 7th Annual ACM-SIAM Symposium on Discrete Algorithms, pp.175-183 (1996).
• [5] Demaine, E.D. and O'Rourke, J.: Geometric Folding Algorithms: Linkages, Origami, Polyhedra, Cambridge University Press (2007).

タイトルに関連する用語 (8件)： 山 ,  谷 ,  割当て ,  鋭角 ,  ジグザグ折り ,  ストリップ ,  平坦 ,  折畳み