A diameter-based model of the rectilinear partitioning problem in VLSI physical design

The rectilinear point-partitioning problem in VLSI physical design can be stated as follows: Given n points in the plane and a number p with 1 <= p < n/2, find p disjoint axis-parallel rectangles R-1, R-2, ..., R-p containing these n points so that the total area of the rectangles is minimized. This area-based model may suffer from the degenerate case where areas of some rectangles vanish. This case is meaningless in VLSI physical design. Moreover, the sizes of rectangles may have great difference in an optimal solution. It is well known that there are several optimization criteria in integrated circuit design (such as area, wirelength, cross number, etc). This paper proposes a new model by replacing the objective function from the total area to the maximum diameter of the rectangles. Our main result is to present improved algorithms, in which the time complexity of a partitioning procedure is reduced from O(n) to O(log n).