An efficient algorithm for analysis of non-orthogonal layout
Nick P. van der Meijs, A.J. van Genderen · 2003
A new algorithm for analysis of nonorthogonal layout is presented. The algorithm is a combination of the scanline and the corner stitching technique. It performs a directed enumeration of all tiles and pairs of abutting tiles that are retained only in a narrow band of adjustable width sweeping over the artwork. The enumeration provides a clean interface to many layout analysis tasks, such as design rule checking and circuit extraction. With N representing the size of the input, the expected-case time and space complexities of the algorithm are O(N) and O( square root N), respectively.>