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:
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.