詰め込み問題に対する球モデルによるアプローチ

概要

詰め込み問題とは、与えられた図形を容器の中に図形の重複がないように配置する問題です。図形の種類、配置の制約、容器の形状などにより様々なバリエーションがあり。広く応用のある重要な問題です。私たちはこの問題に対する汎用的なフレームワークとして、配置する図形を二次元なら円、三次元なら球の集合で近似することで、任意の図形の自由回転を許す状態での配置を求めるというアプローチを提案しています。

URL

http://www-or.amp.i.kyoto-u.ac.jp/res-packing.html

産業界への展開例・適用分野

服飾産業において、私たちの結果を用いて型紙の効率的な配置を求めることにより、部品を取るのに必要な布の量をより少なくするという応用が考えられます。また、可視化の分野では、図形の重複がないよう配置を求めることにより、スクリーン上に効率的に図形を表示させることも可能です。

展示責任者

氏名: 今道 貴司

所属: 情報学研究科・数理工学専攻・離散数理（永持研）

役職: 博士後期課程２年