Construction of the Voronoi diagram for a set of points in the plane has become one of the standard problems in computational geometry. The problem is simply stated: Given a set of generating points, we are asked to divide the plane into regions such that each region contains one generator and encloses all positions closer to that generator than to any other generating point. These regions are polygons when the Euclidean distance metric is used.

Algorithms with a worst-case time complexity of :I0(:In²) and :I0( :In log :In), where :In is the number of generators, have been published over the past several years. The algorithm presented in this paper has worst-case complexity of :I0(:In²), but it appears to have average-case complexity of :I0(:In). The algorithm proceeds by developing the Voronoi diagram incrementally. That is, a diagram for :Ik generating points is amended to incorporate a :Ik+1:U-th point, and so on. The trick lies in choosing a suitable order to process the generating points. The authors have developed an ordering algorithm using quaternary (degree 4) trees. The ordering is chosen so that one point near the center of each quadrant of the plane is processed; then the four quadrants themselves are divided into four quadrants and the process is repeated.

The timing data given by the authors is quite impressive and certainly indicates linear average time performance. Pesumably, the performance is dependent on the points being fairly uniformly distributed. If anyone needs a fast algorithms to handle tens of thousands of points, this one would be a good choice and would also be fairly easy to implement.