与えられた複数の物を、限られた領域、もしくは出来るだけ小さい領域にパッキングするという問題は、様々な場面、例えば、カバンや車に荷物を詰め込むとき、板などの素材から指定された形状の部品を切り出さねばならないときなどに出くわします。それだけでなく、この問題に様々な条件を加えた問題は集積回路設計などにおいて、高性能な集積回路を低コストで生産するため、効率良く解けることが望まれています。
　このパッキング問題に対して密な解を求める方法は幾つかありますが、その中でも有力なものの一つが、素材同士が重ならないことを保証して素材の相対位置関係を与えるというトポロジカルな表現を用いて、密なパッキングを探索する方法です。我々は、この方法に基づいて効率良く密な解を見つけ出す方法についての研究を行っていますが、そのためには、良い表現方法を作り出すことが最も重要です。そして、様々なパッキング問題の中で、我々は既に、

(1) 与えられた複数の長方形を長方形内に詰めるパッキング問題、

(2) 内角が全て90度もしくは270度な多角形であるレクトリニア多角形が複数与えられ、これらを長方形内に詰めるパッキング問題、

(3) マーキングと呼ばれている、複雑な形状である洋服の型紙を複数与えられ、これらを布地にパッキングする問題、

(4) 与えられた複数の直方体を直方体内に詰める3次元のパッキング問題、

について研究を行っており、成果を得ております。

We sometimes have to pack some given objects into a region of given size, or into a smallest region, when some given boxes should be packed into a suitcase or a car, or when some parts of given shapes should be obtained from a plate by cutting. Since this problem, called "packing problem", is a basic problem of layout design of LSI, it is also very important to solve it efficiently in industry.
     To solve the packing problem, several methods are proposed and studied. One of the famous methods is to represent packings by topological representations and to search for representations corresponding to good packings by stochastic search algorithm. Our researches are based on the topological representation, and our research targets include:

(1) rectangle packing,

(2) rectilinear polygon packing (interior angles of the polygon are 90 or 270 degrees only),

(3) "marking", which is to pack paper patterns of clothes,

(4) rectangular box packing (3-dimensional packing).