04/01/1998 09:00 AM
Computer Engineering
Due to layout or specific physical requirements, macro blocks can be in an arbitrary rectilinear shape. Block packing problem will no longer be limited to the rectangle packing. So far no efficient algorithm has been proposed to solve the general rectilinear block packing problem. This paper presents a novel representation method for arbitrary shaped rectilinear blocks in a sequence pair structure. A sequence pair is feasible if an optimal packing of arbitrary rectilinear blocks can be guaranteed for the given sequence pair regardless of the dimensions of the blocks. In this paper, three conditions are derived on a sequence pair which are necessary and sufficient for a sequence pair to be feasible. Furthermore this paper shows that there always exists a feasible sequence pair for a packing of convex rectilinear blocks. As such, the optimal solution for convex rectilinear block packing can be found by exhausting the finite number of feasible sequence pairs. Three sequence pair operations are developed to incrementally change a solution. Each operation takes linear time and generates a feasible sequence pair. An important theoretical result demonstrates that the optimal solution can always be reachable through a finite times of the sequence pair operations. Therefore a stochastic search based on the three operations can search the feasible solution space both continuously and exhaustively. In such a way, for the first time, the arbitrary shaped rectilinear block packing is solved by using a sequence pair structure.
