Recursive Cutting of Rectangular Partitions for VLSI Floorplanning

Rectangular partitionings form a mathematical base for many modern approaches to automation of VLSI design [1-3]. In particular, popular methodologies of hierarchical placement (by cell grouping / merging) as well as procedures of global routing and layout compression deal with partitions that can be hierarchically subdivided into components of bounded complexity.

The article shows that some tight placements cannot be generated by any pairwise merging procedure in the class of isotetically convex blocks.

Isotetically convex blocks (here called blocks, for simplicity) are well described in [4,5]. A block P is a closed polygon whose boundary consists of line segments parallel to coordinate axes, and every horizontal or vertical segment connecting any two points of the polygon P belongs to P. Rank r of block P is the minimal number of rectangles R1, R2, …, Rr which do not intersect block P and complete it to rectangle. In other words: