A resizing algorithm for LSI layout with diagonal edges

Resizing is an operation where expansion or contraction of the pattern is p erformed. Large numbers of patterns that compose the mask pattern of ICs ha ve closed regions confined by edges which are parallel to the x- or y-axis; but to increase the density of integration and improve the circuit perform ance, we sometimes have to use diagonal edges. For resizing of such mask pa tterns, we here propose a resizing algorithm in which a group of patterns c ontaining some diagonal edges is processed in a calculation time of O(N log N) for N vertices. In this algorithm, intermediate sequences of vertices, known as provisional figures, are generated from the input figures, and the output figures are obtained by ORing these provisional figures. This metho d has the merit that the algorithm can be simplified and faster processing is possible with the help of provisional figures. (C) 2001 Scripta Technica .