Voronoi图算法及其在混合电路的衬底耦合研究中的应用

AN ALGORITHM FOR VORONOI DIAGRAM ON INTEGRATED CIRCUIT SUBSTRATE COUPLING SIMULATION

提出了对版图进行划分的Ｖｏｒｏｎｏｉ图的算法：将Ｖｏｒｏｎｏｉ图进行变换，通过扫描技术，从下到上对每个点与交点进行处理，从而形成变换后的Ｖｏｒｏｎｏｉ图，最后将此图转换为Ｖｏｒｏｎｏｉ图．在计算中，针对集成电路的物理特性，改进了阱区附近的Ｖ图的生成以及多个水平位置点和兼并问题．算法时间复杂度为Ｏ（ｎｌｏｇｎ），空间复杂度为Ｏ（ｎ）．

An algorithm for Voronoi diagram on Integrated Circuit Substrate Coupling Simulation is introduced. The algorithm computes a geometric transformation of Voronoi diagram with sweepline technique. From down to top, by dealing with each site, the transferred Voronoi diagram is constructed. Since the algorithm is linked to Circuit layout, it can compute Voronoi diagram near wells which is suitable for IC physical feature. It can also be used in the case where there are four or more cocircular and /or not unique bottommost sites.