A trapezoid-based scanline algorithm for VLSI layout analysis.

An algorithm for managing the scanline, based on representing VLSI layout geometries as a collection of trapezoids, is presented in this memorandum. This algorithm virtually eliminates all unnecessary computation present in published circuit extractors employing the scanline algorithm. When it is implemented as an integral part of the GOALIE2 layout analysis system, the algorithm improves its performance by nearly a factor of two. The average-case performance of the new algorithm has been empirically evaluated to be almost linear. Its efficiency can be appreciated by noting that a VLSI chip with more than 50,000 transistors can be fully extracted in less than half an hour of CPU time on a VAX(TM)-11/8650 computer system. In addition, this algorithm is amenable to parallel processing.