中文摘要：

Voronoi图是计算几何中的一种重要几何结构，也是计算几何的重要研究内容之一，如今已经在图形学、地理信息系统、机械工程、机器人等领域得到广泛应用。增量法是最常用的构造Voronoi图的方法，但一般实现方法中点的定位时间比较长。扫描线算法可以视为一种特殊的增量法，时间复杂度为0（nlogn），但需要构造比较复杂的数据结构。为了更有效地构建Voronoi图，提出了一种改进的Voronoi罔增量构造算法，该算法是通过对已有的生成Voronoi图的增量法进行分析，并结合它们的优点，采用扫捕线的方式，通过右凸链的结构来定位新插入的点，实现了Voronoi图的逐步构造。和扫描线算法类似，其时间复杂度为0（nlogn），但算法更简洁，且便于理解和编程实现。

英文摘要：

Voronoi diagram（VD） is a very important geometry structure and an important research topic in computational geometry. It has been widely applied in computer graphics, GIS, machine engineering and robotics and so on. Incremental algorithm is one of the most popular algorithm to construct VD. To find the location of a new insertion site is a key problem and usually costs lots of time. Sweep-line algorithm can be seen as a special incremental algorithm, which spends O（ nlog n） time to locate a insertion point. In this paper, an improved incremental algorithm for constructing the VD of a planar point set is presented. A new data structure named right convex hull chain is used to find the location of a new input site in O（nlog n） time. Compared with other incremental algorithms, this algorithm can also run in 0 （ nlog n） time, but it＇ s simpler, more comprehensible and easier to implement.