An O (N log N) Algorithm for Boolean Mask Operations

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.