Patent Document ID: 8276102
Application ID: 12718567
Patent Flag: 1

Claim One:
1. A computer implemented method for determining a probability of failure of a very-large-scale integration (VLSI) query design, the method comprising the steps of: building a Voronoi diagram comprising a set of shapes that represent the design, wherein each edge of a given one of the shapes represents a separate Voronoi cell in the Voronoi diagram; converting the Voronoi diagram into a rectangular grid comprising 2 t ×2 s rectangular cells, wherein t and s are chosen so that one rectangular cell contains from about one to about five Voronoi cells; computing a probability of failure for each of the cells in the grid; pairwise merging the cells in the grid; recomputing a probability of failure for the merged cells which accounts for a spatial correlation between the cells; and performing the pairwise merging and recomputing steps s+t times to determine the probability of failure of the design, wherein at least one of the steps is performed by computer.