Efficient fracturing of all angle shaped VLSI mask pattern data
✍ Scribed by Georg Pelz; Volker Meyer zu Bexten
- Book ID
- 104305102
- Publisher
- Elsevier Science
- Year
- 1991
- Tongue
- English
- Weight
- 773 KB
- Volume
- 10
- Category
- Article
- ISSN
- 0167-9260
No coin nor oath required. For personal study only.
✦ Synopsis
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.