An O (N log N) Algorithm for Boolean Mask Operations
- 1 January 1981
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
A new algorithm is presented which calculates Boolean combinations (AND, OR, EXOR, AND NOT) between two layers of an integrated circuit layout. Input and output of the algorithm is an edgebased description of the set of polygons which represent the artwork. The algorithm has O (N log N) time and PI Left column, top. space complexity, i.e. it is faster than previously published methods. Moreover, we believe that it is easier to understand and to implement than the previously leading method in the field.Keywords
This publication has 7 references indexed in Scilit:
- Algorithms for Reporting and Counting Geometric IntersectionsIEEE Transactions on Computers, 1979
- LSI Layout Checking Using Bipolar Device Recognition TechniquePublished by Institute of Electrical and Electronics Engineers (IEEE) ,1979
- Topological Analysis for VLSI CircuitsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1979
- Network recognition of an MOS integrated circuit from the topography of its masksComputer-Aided Design, 1978
- Geometric intersection problemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1976
- The automatic recognition of silicon gate transistor geometriesPublished by Association for Computing Machinery (ACM) ,1976
- Derivation of All Figures Formed by the Intersection of Generalized PolygonsBell System Technical Journal, 1972