| A VLSI chip involves hundreds of thousands of gates and their connections. To build computer aids for the chip designers, a representation for the gates is needed. The representation has to be detailed enough for compaction, but should not impose an excessive demand on the amount of computer storage. In this thesis, a realistic representation by X-Y polygons is suggested. An X-Y polygon is a simple polygon with only vertical and horizontal edges. The notions of convexity within the class of X-Y polygons and maximality within the set of rectangles enclosed by an X-Y polygon are introduced. Efficient algorithms to compute the X-Y convex hull of a set of X-Y polygons, all maximal rectangles in an X-Y polygon, and the intersection of two sets of X-Y polygons are discussed. The algorithms are based on the "scan-line" approach. The time complexity of the first algorithm is near optimal, and the other two are optimal. Unlike convex hulls in the Euclidean plane, the X-Y convex hull of a set of X-Y polygons may not exist. The condition under which the X-Y convex hull exists is given and an algorithm for testing if the given set of X-Y polygons satisfies the condition is also presented. |
