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

摘要

提出了对版图进行划分的Voronoi图的算法:将Voronoi图进行变换,通过扫描技术,从下到上对每个点与交点进行处理,从而形成变换后的Voronoi图,最后将此图转换为Voronoi图.在计算中,针对集成电路的物理特性,改进了阱区附近的V图的生成以及多个水平位置点和兼并问题.算法时间复杂度为O(nlogn),空间复杂度为O(n).