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, pp is the number of rectilinear blocks excluding rectangles and nn 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(n2+ℓ3) time, where ℓℓ is the number of rectilinear blocks. If pp 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 pp is constant.