A meta rectangle has several layouts according to the orientation of the horizontal or vertical cut which is used to split the meta rectangle into the two buddies it resulted from. The layout also depends on the alignments of the demand rectangles the meta rectangle contains. The alignments of the demand rectangles are not fixed at any time the algorithm proceeds. For example, if we match two demand rectangles and the resulting meta rectangle has eight essentially different layouts: lies above or left from and both rectangles can be rotated. Figure 2 shows the eight essentially different layouts for a meta rectangle consisting of two demand rectangles.

**Figure 2:**
Layouts for a meta rectangle with two demand rectangles

A single layout of a meta rectangle is represented by a slicing instruction. This is a four dimensional vector (), where and are the length and width of the meta rectangle in its considered layout, is the orientation of the horizontal or vertical cut used to split it and is the point (according to ) where the cut starts.

To describe all possible layouts of a meta rectangle, a shape function is used. Such functions are known from floorplanning problems [Sto 1983], [Ott 1983]. A shape function for a rectangle can be considered as a decreasing, piecewise linear function. The interpretation is that is an upper bound on the length of a (meta) rectangle that has the width . So, if a meta rectangle has been computed which contains a set of demand rectangles and if the dimensions of the stock rectangle are known, the maximal needed -dimension for a layout of the meta rectangle can be found subject to the given width of the stock rectangle.

**Figure:**
Shape function of a demand rectangle

A shape function is considered as a list of slicing instructions. The shape function of a demand rectangle of length and width consists of two slicing instructions . The cut orientation and its starting point is of no use here, but later we will need this information for the cutting of meta rectangles unequal to demand rectangles. In Figure an example of a shape function for a demand rectangle is given.

The shape function of a meta rectangle is calculated by the shape functions of the two demand or meta rectangles it consists of, with the help of the composition procedure: Let and be two shape functions and a slicing instruction of (). The composed slicing instruction for a horizontal resp. vertical cut is:

- horizontal cut:
- vertical cut:

By composing all slicing instructions of with those of , two shape functions and are computed which contain all possible horizontal resp. vertical slicing instructions. Figure 3 shows a horizontal and vertical shape function, resulting from the composition of the shape functions of two demand rectangles. Three slicing instructions per cut orientation are found. This leads to the fact that a layout of the resulting meta rectangle is not included in the list of slicing instructions, if another layout of the same width but a smaller length or the same length but a smaller width exists. Hence, only feasible slicing instructions are stored in the shape function. For example, layout three and four in the upper row and layouts one and two in the lower row of Figure 2 are treated in this way.

**Figure 3:** Shape functions with given cut orientation

**Figure 4:** Minimum shape function

To calculate a single shape function for a meta rectangle, we
take the minimum about and by merging this two functions
and deleting the dominated slicing instructions. For example, a
slicing instruction of is dominated by one of , if
for a given width . If two slicing instructions
of and have the same width and the same length then
we will determine here, that the horizontal cut is chosen.

The maximal number of slicing instructions that have to be stored in a
shape function which is calculated by composing two other shape
functions and is , where denotes
the number of slicing instructions in function (see [Mue 1991]).

Figure 4 shows the minimum shape function of the functions and shown in Figure 3. In this example of calculating the minimum function, no dominated slicing instructions have to be deleted.

Mon Dec 19 14:08:31 MET 1994