THE L∞ VORONOI DIAGRAM OF SEGMENTS AND VLSI APPLICATIONS

THE L∞ VORONOI DIAGRAM OF SEGMENTS AND VLSI APPLICATIONS
Extended Abstract appeared in Proc. 9th International Symposium on Algorithms and Computation, December 1998, Taejon, Korea, LNCS 1533, 9–18.


Author(s):
EVANTHA PAPADOPOULOU
IBM TJ Watson Research Center, P.O. Box 218, Yorktown Heights, NY 10598, USA
evanthia@watson.ibm.com
D. T. LEE
Supported in part by the National Science Foundation under the Grant CCR-9731638, and by the National Science Council under the grants NSC89-2213-E-001-012, NSC89-2219-E-001-002, and NSC89-2219-E-001-003. Also with the Department of Electrical Engineering and Computer Science, University of Illinois at Chicago, Chicago, IL 60607-7053.
Institute of Information Science, Academias Sinica, Nankang, Taipei, Taiwan, ROC
dtlee@iis.sinica.edu.tw

Keyword(s): Voronoi diagram
L ∞ metric
algorithmic degrees
critical areas
VLSI layout

Subject: Computer Science
Mathematics

Source:
International Journal of Computational Geometry & Applications (IJCGA)
Year: 2001 Vol: 11 Issue: 5 (October 2001) Page: 503 - 528


History: Received: 16 May 1999
Revised: 27 December 2000

DOI: 10.1142/S0218195901000626


Full Text: S0218195901000626.pdf
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.