木構造データを用いた直方体パッキング表現手法(信号処理,LSI,及び一般)

概要

論文の詳細を見る
複数の直方体を互いに重なり合うことなく最も体積の小さい直方体内に配置するという直方体パッキング問題は、3次元MCMや3次元VLSI設計、計算資源の動的再構成スケジューリング問題の基本であるために効率よく優れた解を得る手法が求められている。しかしこの問題はNP困難であり、良い近似解を求めるためにその表現方法が求められている。この要求に対し、2次元上での矩形パッキング表現方法を拡張した方法がいくつか提案されているが、表現できない解があったり、冗長な解を多く含んでいて探索効率が悪いなどの問題があった。そこで本稿は、左下詰めパッキングだけを順序付きの多分木によって効率よく表現する"O-Tree"の考え方を基にして、左下手前詰めの直方体パッキングを表現する方法を提案する。また、直方体数nに対し、既存手法ではO(n^2)時間を必要としたデコード手法を,計算幾何学の手法を用いてO(n log n+s)に改善する手法も提案する。但し、sはz方向で重なりのある直方体対の数である。そしてこれらの手法を計算機実装して既存方法と実験比較し、その有効性を確かめる。
社団法人電子情報通信学会の論文
2004-06-11