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

Pei Yung Hsiao, Wu Shiung Feng

Research output: Contribution to journalJournal Article peer-review

6 Scopus citations


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.

Original languageEnglish
Pages (from-to)522-536
Number of pages15
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Issue number5
StatePublished - 05 1990
Externally publishedYes


  • Mask layout compaction
  • VLSI compaction
  • graph generating algorithm
  • plane sweep algorithm
  • quad tree
  • region search


Dive into the research topics of 'Using a Multiple Storage Quad Tree on a Hierarchical VLSI Compaction Scheme'. Together they form a unique fingerprint.

Cite this