OPTIMAL TILE PARTITION FOR SPACE REGION OF INTEGRATED-CIRCUITS GEOMETRY

An optimal tile partition (OTP) is presented for partitioning the spac e region of a VLSI layout plane into rectangular space tiles. It modif ies the corner stitching data structure to optimise the space tile par tition. There is a serious restriction in the original corner stitchin g data structure, i.e. the solid rectangles cannot overlap each other, whereas our OTP allows overlapping. This paper also shows three theor ems with rigorous proofs and experimental results to obtain the minima l number of the space tiles through the OTP. Moreover, a dynamic plane -sweep algorithm based on region query for the OTP has been developed. Using the OTP, the memory efficiency and the local query operations o f the original corner stitching data structure have been enhanced.