Arbitrary convex and concave rectilinear block packing using sequence-pair

It is proved that any packing is represented by a feasible sequence-pair, including arbitrary concave rectilinear blocks, and a packing algorithm is designed as an SA search of the generated sequence-pairs.

Abstract

The sequence-pair was proposed in 1995 as a rep- resentation of the packing of rectangles of general structure. Since then, there have been efforts to expand its applicability over simple rectangles. This paper proposes a unified way to represent the packing of a set of rectilinear blocks, including arbitrary concave rectilinear blocks. Our idea is in the repre- sentation of a general block by a collection of rectangle blocks with additional constraints. Some sequence-pairs of rectangle blocks with such constraints may not be feasible, i.e., there is no corresponding packing. A necessary and sufficient condition of feasible sequence-pair is given by the properties of the horizontal and vertical constraint graphs. Furthermore, it is proved that any packing is represented by a feasible sequence-pair. The condition includes dimensions of blocks involved. If we limit the rectilinear blocks to L-shaped ones, a necessary and sufficient condition can be represented only in terms of the topology of the sequence-pair, without dimensions of blocks. A packing algorithm is designed as an SA search of the generated sequence-pairs. Experimental results show effectiveness of the proposed method. Index Terms—Compaction, layout, packing, placement, se- quence-pair.