Methods and apparatus for extracting capacitances exerted on diagonal interconnect lines in an integrated circuit design

Abstract

Geometric objects, such as polygons, are defined in a multi-dimensional data space, and are represented by data segments. 'N' dimensional hierarchical trees, or 'ng' trees, are generated to organize the data segments into “outside child nodes” and “inside child nodes” in accordance with a discriminator value. One of “n” sides of a polygon is selected as the discriminator value. To create the ng tree, data segments are designated as “outside child nodes” if a data segment is outside the plane defined by the discriminator value, and data segments are selected as “inside child nodes” if the data segment is inside the plane defined by the discriminator value. This process of partitioning data segments into inside child nodes, and outside child nodes is repeated recursively through each level of the ng tree. Techniques to represent diagonal interconnect lines of regions defined in a multidimensional design layout of an integrated circuit are disclosed. Techniques to extract capacitances exerted on diagonal interconnect lines in an integrated circuit (“IC”) design are also disclosed.