重矩形分割の探索のための一考察

摘要

近年、複数の能動層を積層し、複数層に渡る配線のた めにTSV(Through Silicon Via) により層間を貫通配線 した三次元LSI の研究が盛hに行われている。そのフ ロアプラン設計のための配置の表現として、複数の矩形 分割を重ねた重矩形分割[2] と、それの容易な探索のた めにそれを上から透かして見た単層重矩形分割[3] が提 案された。単層重矩形分割に探索のための局所的な変更 を加えた場合、これが単層重矩形分割とならない、つま り、重矩形分割に対応しないことがあるので判別する必 要があるが、局所的な計算のみでの判別が望まれる。 そこで、単層重矩形分割の局所的な変更時に単層重矩 形分割であるかの効率的な判定を目的として、本稿では 分割線同士の交差が許容された矩形分割が単層重矩形分 割であることの必要十分条件を明らかにする。