Minimum Partition for the Space Region of VLSI Layout
Pei‐Yung Hsiao, Chiao-Yi Lin, Chia-Chung Tsai · 2005
optimal tile partition (OTP) is presented for partitioning the space region of a VLSI layout plane into rectangular spacing tiles (SPTs). It modifies the corner stitching (CST) data structure to optimize the spacing tile partition. We are known there is a serious restriction for the original CST data structure: the solid rectangles can not be overlapped with each other, but our OTP does not limit to it. This paper gives theoretical discussion with respect to some experimental results to obtain the minimal number of the SPTs through the OTP. Moreover, a dynamic plane-sweep algorithm based on region query for the OTP has been developed. By using the OTP, the memory efficiency and the local query operations of the original CST data structure has been enhanced.