International Journal of Computational Geometry & Applications · 2001 · 52 citations · 14 references
EngineeringComputer EngineeringComputer ScienceComputational GeometryComputational MechanicsGeometric ModelingPhysical DesignVery-large-scale Integration LayoutVoronoi DiagramsArea ComputationPolygonal RepresentationVlsi ImplementationVoronoi CellsVoronoi Diagram ComplexityVoronoi PolygonsYield Prediction Validation
In this paper we address the L ∞ Voronoi diagram of polygonal objects and present application in VLSI layout and manufacturing. We show that L ∞ Voronoi diagram of polygonal objects consists of straight line segments and thus it is much simpler to compute than its Euclidean counterpart; the degree of the computation is significantly lower. Moreover, it has a natural interpretation. In applications where Euclidean precision is not essential the L ∞ Voronoi diagram can provide a better alternative. Using the L ∞ Voronoi diagram of polygons we address the problem of calculating the critical area for shorts in a VLSI layout. The critical area computation is the main computational bottleneck in VLSI yield prediction.
14