ESTIMATING FREE SPACE IN IC CHIPS

Free space on a routed IC is estimated using expanding hierarchical search quadtrees or octrees. Nodes defining rectangular spaces of a layer are created in the tree. Definitions of polygons representing occupied space in the rectangular space are subtracted from a free-space polygon based on the rectangular space. A cost factor is identified for the node, and the process repeats with additional feature polygons until either the cost factor exceeds a maximum or no further feature polygons exist in the layer. If the cost factor exceeds the limit, the node is fractured into child nodes, each defining a quadrant of the parent rectangular space and each containing polygon definitions from the parent node. The process repeats until either the cost factor for each node is not greater than the limit or a dimension of the rectangular space of the node reaches a selected minimum. The nodes define free spaces, which are summed to identify the free space on the IC layer.