容量限制Power图快速计算算法

摘要：

与Voronoi图不同, Power图有着精确限容的特性, 可应用于众多领域. 在普通Power图上, 通过给每个站点增加权重来添加容量限制约束, 即得到容量限制Power图. 现有容量限制Power图的生成算法时间复杂度高, 速度较慢. 本文首先对Power图权值对于容量的单调性进行理论证明, 然后提出了一种Power图权值的快速计算方法, 相比于现有的试位法, 能大幅提升容量限制 Power 图的生成性能. 实验结果表明, 文中算法具有速度快, 精确度高, 便于计算, 密度适应性强等优点.

关键词：Power图、容量限制剖分、质心Power图、解析法

所属期刊栏目：30

分类号：TP391.41(计算技术、计算机技术)

资助基金：国家重点研发计划项目2016YFC0800100;安徽省科技强警项目1704d0802177

在线出版日期：2018-06-12（万方平台首次上网日期，不代表论文的发表时间）

页数：共10页

页码：791-800