Geographic Access Engine for Layout Design: Part I
The presented GA Engine is bin array based and can solve numerous rectilinear geometry computation in O(N) time, including geometric operations like reverse, merge, enlarge, shrink, contour, smooth and maximize-area. All operations are based on a fact: shapes decomposed in same direction can be merged in O(N) time with the help of constant time RQ. To process 100+ million shapes, the GA Engine needs to take both algorithm and SW engineering challenges. Without getting into programming details, some SW architecture concerns are also addressed in this presentation. As an example, we'll show how to construct an O(N) rectilinear polygon engine from this GA Engine.
Mingfu Gong and Yanyan He, Synopsys, Inc.