New algorithms based on a multiple storage quadtree for hierarchical compaction of VLSI mask layout

This paper presents the algorithms, implementation, and performance of a hierarchical mask compactor based on a fast region-query and space-efficient data structure called the multiple storage quadtree. Unlike symbolic compaction, the proposed mask compaction is based on rectangles rather than symbols. A new method of generating the constraint graph by using a sweeping-line algorithm in two-dimensional space is proposed in detail. Some important features of the mask compactor, such as error tolerance, mixed constraint, grid freeness, and hierarchical design and amalgamation, are described. Experimental results show that the proposed system successfully accomplishes layout compaction with almost linear time complexity in terms of the rectangles in the source layout.