Patent ID: 6877013

Claim:
A method of extracting capacitances exerted on diagonal interconnect lines in an integrated circuit (“IC”) design, wherein a diagonal interconnect line defines a line deposed in a direction other than zero or ninety degrees relative to the integrated circuit boundaries, wherein a computer system stores an IC design layout and uses geometric objects to represent diagonal interconnects lines in the layout, and wherein the computer system represents each geometric object by a geometric data segment, the method comprising: a) defining a plurality of regions in the multidimensional layout; b) creating a plurality of hierarchical data structures for a number of said regions, wherein each hierarchical data structure corresponds to a separate region; C) for each geometric object in the layout, identifying a region that the geometric object intersects and the hierarchical data structure corresponding to the identified region; and inserting the geometric data segment of the geometric object in the identified hierarchical data structure.