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 O(nlog n) time

but it’s simpler

more comprehensible and easier to implement.