シーケンスペア
シーケンスペアはそれ単独では単なる表現方法に過ぎない。しかし先述のスライス構造と同様に、焼きなまし法などの確率的探索アルゴリズムと組み合わせて用いることで、矩形パッキング問題に対し、準最適な配置を実用的な時間で求めることができる。最近ではシーケンスペアを用いた配置検討工程の応用例として、バス配線経路をモジュール配置制約として与えた配置手法や、アナログ回路設計特有のモジュール配置制約を課した手法などが発表されている。
集積回路設計以外では、建築設計における室配置計画への応用も報告されている。 またシーケンスペアは矩形しか扱えないが、矩形の集合で表現できる多角形、すなわち垂直もしくは水平線分で描かれる多角形(レクトリニア多角形と呼ぶ)はパッキング可能である。これを利用すると、任意の多角形をレクトリニア多角形に近似すれば、例えば自動車の板金や洋服の型紙を効率よく切り出すパターンの探索が可能になる。
集積回路設計の一工程である配置計画(フロアプラン)では、回路として実現するために必要な様々なモジュール(記憶素子や演算器など)を、シリコン基板上にどのように配置するかを検討する。半導体ビジネスでは、1枚のシリコンウェハーから出来るだけ多くの集積回路(IC, LSI)を製造することが収益面で不可欠である。そのため、集積回路そのものを出来るだけ小さく設計することが望まれる。
「集積回路を出来るだけ小さく設計する」という要求は、配置計画において「モジュールを互いに重なることなく、出来るだけ小さい矩形領域内に配置する」という要求に置き換えられる。近年の集積回路設計では、性能及び生産性向上の観点から複雑な配置制約を課されるため、単に隙間無く配置すればよいわけではない。しかし、隙間無く配置する作業はモジュールが数個から十数個程度であればまるでパズルのようだが、これが数百、数千、それ以上となると、とても人間が手に負える規模ではないことが明らかだろう。
このスライス構造をフロアプラン問題に応用したのが、テキサス大のD.F. Wongとイリノイ大のC.L. Liuの二人である。Ottenの提唱したスライス構造のデータが多分木であったが、1986年にWongらは水平線分による分割であれば+記号を、垂直線分による分割であれば*記号を木の節点に与えて二分木表現にした。そして、この二分木の各々の葉に分割後の各領域に割り当てるモジュールの名前をつけ、この木をスライス木と呼んだ。ちなみにスライス木は全二分木(full binary tree)、すなわち全ての節点が葉であるか、2つの子を持つ。また、同じスライス構造を表現するスライス木が複数存在するが、親と右の子が同じ*もしくは+記号を持たないスライス木を、非平衡スライス木(skewed slicing tree)と呼ぶ。図2はスライス構造と、それに対応する非平衡スライス木の例である。