A fast algorithm for rectilinear block packing based on selected sequence-pair
In this paper, we present a method of rectilinear block packing using selected sequence-pair (SSP), a rectangle packing representation. We also propose a fast algorithm to obtain a rectilinear block packing in O((p+1)n) O ( ( p + 1 ) n ) time keeping all the constraints imposed by a given SSP. Here, p p is the number of rectilinear blocks excluding rectangles and n n is that of rectangle sub-blocks obtained by partitioning each rectilinear block. So far, the fastest method based on a sequence-pair required O(n2+?3) O ( n 2 + ? 3 ) time, where ? ? is the number of rectilinear blocks. If p p is constant, the proposed algorithm requires O(n) O ( n ) time, which is equal to the trivial lower bound of the time complexity for decoding. The effectiveness of the proposed method was confirmed by the experimental comparisons, especially when p p is constant.
rectilinear block packing selected sequence-pair sequence-pair placement floorplan