EFFICIENT GENERATION OF DIAGONAL CONSTRAINTS FOR 2-D MASK COMPACTION

We propose a new efficient constraint generation technique for 2-D mas k compaction based on Branch-and-Bound Optimization (BBO), To assure s eparation in X and Y between rectangles in a layout, we generate the s o called ''diagonal'' constraints in addition to the usual simple cons traints in the X and Y directions. A diagonal constraint consists of t wo constraints, one in each dimension, Our method determines areas aro und the rectangles beyond which the diagonal (and the simple) constrai nts need not be generated, producing thus a nearly irredundant system of constraints. During BBO, the diagonal constraints are treated as du al constraints, in which case, one of the two component constraints of the dual can be deactivated, When a such constraint is deactivated, f ew additional constraints must be be added to assure a legal layout, T he overall performance is still considerably improved, because there a re fewer dual constraints. Proofs of sufficiency are based on a novel characterization of the 2-D constraint structure.