凸多面体の重なりを持たない展開図の数え上げ

• Item type: SIG Technical Reports(1)
• 公開日: 2024-11-19
• タイトル: 凸多面体の重なりを持たない展開図の数え上げ
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 九州工業大学／日本学術振興会
• 著者所属: 北海道大学
• 著者所属: 北海道大学
• 著者所属: 北海道大学
• 著者所属: 北陸先端科学技術大学院大学
• 著者所属: 九州工業大学
• 著者所属: 北陸先端科学技術大学院大学
• 著者名: 塩田, 拓海; 榎本, 優大; 五郎部, 誠士; 堀山, 貴史; 鎌田, 斗南; 斎藤, 寿樹; 上原, 隆平
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 多面体を切断線に沿って切り開く操作を展開と呼び，それによって得られる多角形を展開図という．展開図の形状は展開方法によって異なり，その個数は切断線によって形成される切断木の個数と一致する．一方，多面体や展開方法によっては得られる展開図の一部の面が他の面と重なりを持ち，平面上に埋め込むことができない．Shevon は，切断線を辺に制約した辺展開図について，頂点の数が多くなるほど，重なりを持たない辺展開図の割合が少なくなることを実験的に示した．しかし，この実験はランダムに選択した 1000 個の辺展開図に対する割合であり，重なりを持つ展開図と持たない展開図がそれぞれいくつあるのか，また比率がどのような値であるかについては解明されていなかった．多面体の（重なりを持つものを含む）展開図の個数を数え上げる手法として，集合族をコンパクトなデータ構造として扱うゼロサプレス型二分決定グラフ（ZDD）がある．ZDD は集合族に対する代数演算を提供しており，例えば，ZDD 上で特定の制約を満たす集合を効率的に抽出することが可能である．本研究では，ZDD とその上の演算を利用し，重なりを持たない展開図の個数を数え上げるアルゴリズムを提案する．これは，まず塩田と斎藤が提案した回転展開によって得られる極小な重なりを持つ部分展開図（MOPU）を列挙する．その後，すべての展開図を表す ZDD から，MOPU から構築される ZDD を差し引くことで，重なりを持たない展開図を表す ZDD を構築する．我々は，このアルゴリズムを，切断線を多面体の辺とした辺展開および，面を単位正方形の辺に沿って切り開いて得られる格子展開に適用し，いくつかの凸多面体における重なりを持たない展開図の個数を示す．
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2024-AL-200, 号 11, p. 1-8, 発行日 2024-11-19
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8566
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会