2026-03-13T21:08:48Z https://ipsj.ixsq.nii.ac.jp/oai

oai:ipsj.ixsq.nii.ac.jp:00241027 2025-01-19T07:46:01Z 1164:2592:11452:11789

凸多面体の重なりを持たない展開図の数え上げ 塩田, 拓海 榎本, 優大 五郎部, 誠士 堀山, 貴史 鎌田, 斗南 斎藤, 寿樹 上原, 隆平 多面体を切断線に沿って切り開く操作を展開と呼び，それによって得られる多角形を展開図という．展開図の形状は展開方法によって異なり，その個数は切断線によって形成される切断木の個数と一致する．一方，多面体や展開方法によっては得られる展開図の一部の面が他の面と重なりを持ち，平面上に埋め込むことができない．Shevon は，切断線を辺に制約した辺展開図について，頂点の数が多くなるほど，重なりを持たない辺展開図の割合が少なくなることを実験的に示した．しかし，この実験はランダムに選択した 1000 個の辺展開図に対する割合であり，重なりを持つ展開図と持たない展開図がそれぞれいくつあるのか，また比率がどのような値であるかについては解明されていなかった．多面体の（重なりを持つものを含む）展開図の個数を数え上げる手法として，集合族をコンパクトなデータ構造として扱うゼロサプレス型二分決定グラフ（ZDD）がある．ZDD は集合族に対する代数演算を提供しており，例えば，ZDD 上で特定の制約を満たす集合を効率的に抽出することが可能である．本研究では，ZDD とその上の演算を利用し，重なりを持たない展開図の個数を数え上げるアルゴリズムを提案する．これは，まず塩田と斎藤が提案した回転展開によって得られる極小な重なりを持つ部分展開図（MOPU）を列挙する．その後，すべての展開図を表す ZDD から，MOPU から構築される ZDD を差し引くことで，重なりを持たない展開図を表す ZDD を構築する．我々は，このアルゴリズムを，切断線を多面体の辺とした辺展開および，面を単位正方形の辺に沿って切り開いて得られる格子展開に適用し，いくつかの凸多面体における重なりを持たない展開図の個数を示す． 情報処理学会 2024-11-19 jpn technical report https://ipsj.ixsq.nii.ac.jp/records/241027 2188-8566 AN1009593X 研究報告アルゴリズム（AL） 2024-AL-200 11 1 8 https://ipsj.ixsq.nii.ac.jp/record/241027/files/IPSJ-AL24200011.pdf application/pdf 854.5 kB 2026-11-19