Critical area computation for missing material defects in VLSI circuits

We address the problem of computing critical area for missing material defe cts in a circuit layout. The extraction of critical area is the main comput ational problem in very large scale integration yield prediction. Missing m aterial defects cause open circuits and are classified into breaks and via blocks. Our approach is based on the L-infinity medial axis of polygons and the weighted L-infinity Voronoi diagram of segments. We also introduce the min-max Voronoi diagram of rectangles, a combinatorial structure of indepe ndent interest. The critical area problem for breaks and via blocks is redu ced to variations of weighted L-infinity Voronoi diagram of segments. Plane sweep algorithms to compute the appropriate Voronoi diagrams for each case are presented. As a result, the critical area for breaks and via blocks on a single layer can be computed accurately in one pass of the layout, The t ime complexity is O(n log n) in the case of breaks and O((n + K)log n) in t he case of via blocks, where n is the size of the input and K is upper-boun ded by the number of interacting vias tin practice K is small), The critica l area computation assumes square defects and reflects all possible defect sizes following the D(r) = r(0)(2)/r(3) defect size distribution. The metho d is presented for rectilinear layouts.