Method for generating an optimized nested arrangement of constrained rectangles
First Claim
1. A method for allocating rectangular areas for given elements on a rectangular surface of a product such as an integrated circuit, each element being limited by a shape constraint and related to the other elements by proximity information, comprising the steps of:
- deriving a distance space to position a center of each said element on said product surface in a configuration of points in a plane;
constructing a slicing structure from said point configuration of said element centers;
determining from the result of the above steps the dimensions, position, and orientation of said elements; and
dividing up said product surface accordingly.
1 Assignment
0 Petitions
Accused Products
Abstract
The overall arrangement of a number of non-overlapping rectangles with constraints on their size and shape, may be generated with relation to a number of objective functions such as, size and shape of the enveloping rectangle, size of an interconnecting network, and distance between pairs of individual rectangles, by first embedding a distance space, reflecting the desired proximity structure, in the plane; next, by refining containment relations, fixing the relative positions of rectangles within such a containment in accordance with the corresponding positions in the embedding; and on the basis thereof estimating the space required for the local realization of the interconnecting network in a configuration satisfying the constraints on the individual rectangles, and optimal with respect to any quasi-concave objective function on the dimensions of the enveloping rectangle that is monotone in its arguments. The method can be implemented even on relatively small computers. Its major application is in the generation of mask patterns of complex semiconductor integrated circuits, especially when a given functional structure must be preserved by containment in rectangles.
-
Citations
24 Claims
-
1. A method for allocating rectangular areas for given elements on a rectangular surface of a product such as an integrated circuit, each element being limited by a shape constraint and related to the other elements by proximity information, comprising the steps of:
-
deriving a distance space to position a center of each said element on said product surface in a configuration of points in a plane; constructing a slicing structure from said point configuration of said element centers; determining from the result of the above steps the dimensions, position, and orientation of said elements; and dividing up said product surface accordingly. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24)
-
Specification