Options
1991
Journal Article
Titel
Efficient fracturing of all angle shaped VLSI mask pattern data
Abstract
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.