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

• 作者: 梁峭岩 胡俊 蒋慧文 黄均鼐
• 来源期刊: 计算机辅助设计与图形学学报
• 学科: 工学
• 关键词: Voronoi图 数模混合集成电路 数值模拟
• 年，卷（期）: 1999,（2）
• 所属期刊栏目: 电子设计自动化
• 页码范围: 139-142
• 页数: 4页
• 分类号: TB11|TN47|TP391.7
• 字数: 3649字
• 语种: 中文
• DOI: 10.3321/j.issn:1003-9775.1999.02.011

摘要

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