講演抄録/キーワード |
講演名 |
2015-10-06 09:30
可変成形型電子ビーム露光装置のためのサイズ上限を考慮した矩形分割手法 ○長谷川 充・藤吉邦洋(東京農工大) CAS2015-34 NLP2015-95 |
抄録 |
(和) |
LSIのマスク製造に広く用いられている可変成形型電子ビーム露光装置は矩形に成形した電子ビームを照射するため、入力であるレイアウト上のレクトリニア多角形を、指定された大きさ以下で出来るだけ少ない数の矩形の集合に分割する処理が必要となる。この問題に対して、Kahngらは整数線形計画法を用いた手法と発見的な手法を提案したが、超多項式の計算時間がかかったり、単純な問題でも最小数の矩形に分割できない場合がある。そこで本稿では、レクトリニア多角形を指定された大きさ以下で最小数の矩形に分割することを多項式時間でどこまでできるのかを明らかにすることを目的とし、レクトリニア凸多角形の凹頂点を通るスライス分割線優先で再帰的に分割するという方針のもと、動的計画法を用いた分割手法を提案する。そして、レクトリニア凸多角形の分割がその頂点数に対して多項式の時間にてできることを示し、計算機実験によりその動作を確認する。 |
(英) |
Since variable shaped-beam mask writing machines for LSI mask production can expose a rectangle shaped-beam, we need to partition rectilinear polygons in layout into a set of rectangles of the minimum number with considering size limit. For this problem, Kahng proposed an ILP method and a heuristic method. However, the former needs super-polynomial time and the latter may not obtain the optimum solution. In this paper, we propose a new fracturing method for convex rectilinear polygons using dynamic programming, which cut each polygon by slicing-lines through concave vertices firstly. The proposed method can solve the problem in polynomial time though it uses $O(n^4)$ memories in the worst case. Computer experiments confirm the space and time complexity of the method. |
キーワード |
(和) |
多角形分割 / EB露光装置 / マスクデータ / 動的計画法 / / / / |
(英) |
Polygon Fracturing / EB writing / mask data / Dynamic Programming / / / / |
文献情報 |
信学技報, vol. 115, no. 239, CAS2015-34, pp. 69-74, 2015年10月. |
資料番号 |
CAS2015-34 |
発行日 |
2015-09-28 (CAS, NLP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
CAS2015-34 NLP2015-95 |