Rectilinear block packing using O-tree representation

Abstract

In this paper we extend the O-tree approach to handle rectilinear blocks. First we explore the properties of L-shaped blocks, then decompose rectilinear blocks into a set of sub-L-shaped-blocks. The properties of L-shaped blocks can be applied to general recti?linear blocks. In order to explore the optimal search thoroughly, we generate four direction O-trees. A heuristic optimization algorithm based on the four direction O-trees produces very good experiment results.