Using hierarchical multiple storage quad trees on a constraint-graph layout compaction

In the last decade several primitives of quad trees have been proposed as data structures for the hierarchical design of VLSI. This paper presents algorithms, implementation, and experimental results of a hierarchical mask layout compaction scheme based on a fast region-query and space-efficient data structure called the hierarchical multiple storage quad tree. Contrary to symbolic compaction, this mask layout compaction is based on rectangle edges rather than symbols. A new method for the generation of a constraint-graph is proposed in detail by using an alternative dynamic event scheduling algorithm (DES algorithm) in 2-D space. This is a new plane sweep method based on the multiple storage quad tree and is capable of being extended to support the inherent problems in computational geometry and image processing. Some important features of the mask layout compactor: Such as error-tolerance, mixed-constraint, grid-freeness, and hierarchical design and amalgamation, are described in this article. In consequence, we have successfully accomplished the layout compactor in practical linear time performance in terms of the rectangles in the VLSI layout.