Title :
An efficient sequential range query model for minimum width/space verification (circuit analysis)
Author :
Jeong, J.C. ; Shin, S.Y. ; Lee, C.D. ; Yu, Y.U.
Author_Institution :
Electron. & Telecommun. Res. Inst., Chungnam, South Korea
Abstract :
An algorithm which efficiently reports minimum width/space violation in a geometric mask pattern is presented. The algorithm solves a sequence of range research problems by using a plane sweep method. The algorithm runs in O(n log n) time, which is very efficient in practice. Moreover, the algorithm is easy to implement and has practical speed (116.7 for a rectilinear region with 2.5*10/sup 5/ vertices on the VAX 8650).<>
Keywords :
circuit analysis computing; circuit layout CAD; VAX 8650; algorithm; circuit analysis; geometric mask pattern; minimum width/space verification; minimum width/space violation; plane sweep method; range research problems; rectilinear region; sequential range query model; Circuit analysis; Circuit optimization; Design methodology; Search problems; Solid modeling; Space technology; Statistics; Transistors; Very large scale integration;
Conference_Titel :
Computer-Aided Design, 1988. ICCAD-88. Digest of Technical Papers., IEEE International Conference on
Conference_Location :
Santa Clara, CA, USA
Print_ISBN :
0-8186-0869-2
DOI :
10.1109/ICCAD.1988.122522
