Time efficient VLSI artwork analysis algorithms in GOALIE2
Kuang-Wei Chiang, Surendra Nahar, Chi-Yuan Lo · Design Automation Conference · 1988
New algorithms used in the GOALIE2 circuit extraction system, based on representing VLSI layout geometries as trapezoids, are presented in this paper. These include polygon-to-trapezoid decomposition, scanline management, and output sorting. In particular, the scanline algorithm virtually eliminates all redundant computation present in similar systems. These algorithms enable us to perform VLSI layout analysis in nearly linear time.