Using a Multiple Storage Quad Tree on a Hierarchical VLSI Compaction Scheme

This paper presents a new graph generating algorithm and the experimental results of a hierarchical mask layout compaction scheme based on a new plane sweep algorithm and a fast region-query and space-efficient data structure called the hierarchical multiple storage quad tree. For a mask layout design, a rectangle is used as the primary element of the layout. Hence, in our hierarchical mask compaction scheme, the graph generating algorithm is based on the edges of rectangles rather than the central lines of symbols for the symbolic compaction design. The new plane sweep algorithm developed in this paper is also called a dynamic event scheduling algorithm which can be applied to solve some other problems in the field of computational geometry and image processing. The efficiencies of both of the plane sweep algorithm and the graph generating algorithm arc dependent on the region query operations of the spatial data structure. By using the improved multiple storage quad tree as the spatial data structure in our system, we have successfully accomplished the mask layout compactor in a practical linear time performance in terms of the rectangles in the source layout.