可変成形型電子ビーム露光装置のためのサイズ上限を考慮した矩形分割手法

摘要

LSIのマスク製造に広く用いられている可変成形型電子ビーム露光装置は矩形に成形した電子ビームを照射するため、入力であるレイアウト上のレクトリニア多角形を、指定された大きさ以下で出来るだけ少ない数の矩形の集合に分割する処理が必要となる。この問題に対して、Kahngらは整数線形計画法を用いた手法と発見的な手法を提案したが、超多項式の計算時間がかかったり、単純な問題でも最小数の矩形に分割できない場合がある。そこで本稿では、レクトリニア多角形を指定された大きさ以下で最小数の矩形に分割することを多項式時間でどこまでできるのかを明らかにすることを目的とし、レクトリニア凸多角形の凹頂点を通るスライス分割線優先で再帰的に分割するという方針のもと、動的計画法を用いた分割手法を提案する。そして、レクトリニア凸多角形の分割がその頂点数に対して多項式の時間にてできることを示し、計算機実験によりその動作を確認する。