Title: Critical Area Computation via Voronoi Diagrams Evanthia Papadopoulou IBM TJ Watson Research Center Post Office Box 218 Yorktown Heights, New York 10598 evanthia@watson.ibm.com and D. T. Lee* Department of Electrical and Computer Engineering Northwestern University Evanston, IL 60208 dtlee@ece.nwu.edu * Supported in part by the Office of Naval Research under the Grants No. N00014-95-1-1007 and No. N00014-97-1-0514. Abstract: In this paper we present a new approach for computing the critical area for shorts in a circuit layout. The critical area calculation is the main computational problem in VLSI yield prediction. The method is based on the concept of Voronoi diagrams and computes the critical area for shorts (for all possible defect radii, assuming square defects) accurately in $O(n\log n)$ time, where $n$ is the size of the input. The method is presented for rectilinear layouts and layouts containing edges of slope $\pm 1$. As a byproduct we briefly sketch how to speed up the grid method of Wagner and Koren \cite{WK95}. Appeared in IEEE Trans. Computer-Aided Design, (18,4):463-474, April 1999.