THE L<sub>∞</sub> VORONOI DIAGRAM OF SEGMENTS AND VLSI APPLICATIONS

Evanthia Papadopoulou, D. T. Lee

International Journal of Computational Geometry & Applications · 2001 · 52 citations · 14 references

Concepts

Abstract

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.

References

14