Fast Evaluation of Bounded Slice-Line Grid

Bounded Slice-line Grid (BSG) is an elegantrepresentation of block placement, because it is very intuitionisticand has the advantage of handling various placement constraints.However, BSG has attracted little attention because its evaluation isvery time-consuming. This paper proposes a simple algorithmindependent of the BSG size to evaluate the BSG representation inO(nloglog n) time, where n is the number of blocks. In thealgorithm, the BSG-rooms are assigned with integral coordinatesfirstly, and then a linear sorting algorithm is applied on theBSG-rooms where blocks are assigned to compute two block sequences,from which the block placement can be obtained in O(nloglog n)time. As a consequence, the evaluation of the BSG is completed inO(nloglog n) time, where n is the number of blocks. Theproposed algorithm is much faster than the previous graph-basedO(n^2) algorithm. The experimental results demonstrate theefficiency of the algorithm.