Efficient design rule checking using a scanline algorithm

Design rule checking of integrated circuits requires many operations which manipulate and test geometric figures. Closer examination often reveals that some effort is duplicated by different operations on the same mask data. The paper describes a scanline based design rule checker which structures the mask data to allow common administrative operations to be separated from the main checking process. This structuring is made possible by a novel data structure, the `scanline history¿, and it is demonstrated experimentally that, after an initial preprocessing phase, the workspace and execution times required to perform design rule checking are 0(N0.5) and 0(N). The results indicate that rationalised scanline administration yields significant savings in overall execution time.