Hier finden Sie wissenschaftliche Publikationen aus den Fraunhofer-Instituten.

Efficient fracturing of all angle shaped VLSI mask pattern data

: Meyer zu Bexten, V.; Pelz, G.

Integration: The VLSI journal 10 (1991), Nr.2, S.143-154
ISSN: 0167-9260
Fraunhofer IMS ()
CAD for VLSI; computational geometry; coverage; dissection; exposure system; fracturing; hierarchical fracturing; pattern generator; plane sweep

Fracturing (i.e., filling area by rectangles) is one of the most important tasks of an artwork system for a pattern generator. Growing chip complexity requires efficient algorithms to perform this non-trivial data transformation. In order to solve this problem, we developed a fracture system using a new approach and improved algorithms. Its key features are the use of plane sweep techniques and the subdivision of the task in processing rectilinear shaped area and all angle shaped area. The manhattan area algorithm supplies an almost optimal rectangle dissection. The coverage of the remaining area is achieved in a good heuristical manner. Both algorithms guarantee to converge and find a complete filling. No restrictions are imposed on the area to be handled. The system has a time complexity of O(n log n). Additionally an outlook on hierarchical fracturing is presented.