The L-infinity Voronoi diagram of segments and VLSI applications

In this paper we address the L-infinity Voronoi diagram of polygonal object s and present applications in VLSI layout and manufacturing. We show that t he L-infinity Voronoi diagram of polygonal objects consists of straight lin e segments and thus it is much simpler to compute than its Euclidean counte rpart; the degree of the computation is significantly lower. Moreover, it h as a natural interpretation. In applications where Euclidean precision is n ot essential the L-infinity Voronoi diagram can provide a better alternativ e. Using the L-infinity 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 predict ion.