Computer Engineering and Applications ›› 2010, Vol. 46 ›› Issue (8): 8-10.DOI: 10.3778/j.issn.1002-8331.2010.08.003

• 博士论坛 • Previous Articles     Next Articles

Improved incremental construction algorithm of Voronoi region

XU Peng-fei1,2,CHEN Zhi-gang2   

  1. 1.College of Mathematics and Computer Science,Hunan Normal University,Changsha 410081,China
    2.College of Information Science and Engineering,Central South University,Changsha 410083,China
  • Received:2009-11-24 Revised:2010-01-11 Online:2010-03-11 Published:2010-03-11
  • Contact: XU Peng-fei



  1. 1.湖南师范大学 数学与计算机科学学院,长沙 410081
    2.中南大学 信息科学与工程学院,长沙 410083
  • 通讯作者: 徐鹏飞

Abstract: This paper transforms the half-plane common collection of Voronoi region into the location relationship of the Voronoi vertex in the half-plane,and presents a simple clipping rule to incrementally construct the Voronoi region.In addition,the algorithm can deal with the Voronoi edge which is the half-line or the line,and can also adapt to collinear nodes.Theoretic analysis and experiment results show that the time complexity of the algorithm is approximately linear.

摘要: 将Voronoi区域的半平面公共交集转换为Voronoi顶点与半平面的位置关系,提出一种简单的裁剪规则实现Voronoi区域的增量构造;该算法可以有效地处理半直线Voronoi边与直线Voronoi边以及节点共线等特殊情况。理论分析与实验结果表明,该增量构造Voronoi区域的平均时间复杂度是近似线性的。

CLC Number: