5/12 - Talk "Voronoi Diagrams, Generalizations, and Applications in VLSI Design for Manufacturing"

Date: 5 December 2008
Time: 10.15 AM
Place: CAB H 56

Voronoi Diagrams, Generalizations, and Applications in VLSI Design for Manufacturing

Evanthia Papadopoulou

The Voronoi diagram is a powerful mathematical object encoding nearest neighbor information with numerous applications in diverse areas.  In this talk I will present my work on generalized Voronoi diagrams, specifically, the Hausdorff Voronoi diagram and higher order Voronoi diagrams of segments, and present applications in predicting the yield of a VLSI chip.  The Critical Area of a VLSI design is a measure reflecting the sensitivity of the design to random defects occurring during the chip manufacturing process. Fast and accurate critical area extraction is essential for modern VLSI manufacturing especially when Design for Manufacturability (DFM) changes are under consideration.  I will address the critical area extraction problem for various types of faults such as shorts, open faults, and via blocks, using our results on generalized Voronoi diagrams.  All algorithms have been integrated into a new IBM-Cadence CAD tool (Voronoi CAA) widely used by IBM Microelectronics for critical area extraction and yield prediction.


Evanthia Papadopoulou is an Associate Professor with the Faculty of Informatics, Università della Svizzera Italiana (University of Lugano). From 1996 to 2008 she had been a Research Staff Member in the Design Automation department at the IBM T. J. Watson Research Center. She holds a Ph.D. in Computer Science from Northwestern University, December 1995, an MS in Computer Science from University of Illinois at Chicago, and a BS in Mathematics from University of Athens, Greece. Evanthia’s research interests are in Design and Analysis of Algorithms, Computational Geometry, Applications of Graph and Geometric Algorithms, VLSI Computer-Aided Design and Manufacturing.

In recent years her research activity has been in the intersection of Analysis of Algorithms, Computational Geometry and VLSI Design Automation. She has worked in the area of Computer-Aided Design for Manufacturability (DFM) applying basic concepts from graph algorithms and computational geometry. She has applied generalizations of Voronoi diagrams such as higher order Voronoi diagrams of polygons, the Hausdorff Voronoi diagram, and others, to address DFM issues in VLSI design such as critical area extraction, assist feature placement, and yield prediction.