An O(nloglogn) algorithm for evaluation of Bounded Slice-line Grid

Bounded Slice-line Grid (BSG) is an elegant representation of block placement/floorplan, because it is very intuitionistic and has advantage of handling various placement constraints. However, BSG has attracted little attention because of its time-consuming evaluation. In this paper, we proposed a simple algorithm to evaluate the BSG assignments in O(nloglogn) time. The BSG room´s is assigned coordinates firstly, and then a linear sorting algorithm is applied on BSG to compute two module sequences, on which packing can be obtained in O(nloglogn) time. Consequently, The BSG can be evaluated in O(nloglogn) time where n is the number of blocks. The experimental results demonstrated the efficiency of our algorithm.