Nested maximum space computation and efficient generation of nested

Abstract

A method of nested maximum space computation is used for the processing of shapes in design data for integrated circuits and printed circuit electronic packages. This method determines the complement of a design level without unnecessary flattening or denesting thereby reducing the processing time and the volume of the output data. Native shapes are first expanded by one-half the maximum space ground rule value to get the expanded native shapes. The nested shape complementation method is applied to the expanded native shapes to get the error candidate shapes. The error candidate shapes indicate areas that are possible violations. Next, the expanded native shapes are subtracted from the error candidate shapes to get the real error shapes. The nested shape complementation method finds the regions between shapes in a hierarchical design without denesting. For each cell that does not have transforms of other cells, the nested shape complementation method finds the cell's proper frame and uses that frame and the cell's native shapes to create complemented shapes. For each cell with transforms of other cells, the nested shape complementation method finds the cell's proper frame and uses that frame, the cell's native shapes, and its transformed cell's frames to create complemented shapes. The complemented shapes are added to the cell as native shapes on a new design level.