Green and Sibson [1] calculated the Voronoi diagram by incremental insertion i.e., obtained V(S) from V(S\{s}) by inserting the site s. As the region of s can have up to (n–1) edges, for n = |S|, this leads to a runtime of O(n²). Ohya, Iri, Murota [2] and Sugihara [3] have polished up the technique of inserting Voronoi regions, and make “incremental algorithm” efficient and numerically robust. In fact, well-distributed sets of sites achieve average time complexity of O(n). The incremental method set up with a simple Voronoi diagram for two or three sites, and modified the diagram by adding sites one by one. For p = 1, 2, . . . , n, let V_p denoted the Voronoi diagram for the first p sites s₁, s₂, . . . , s_p. The major part of the incremental method is to translate V_p-1 to V_p for each p.

The basic idea the incremental Voronoi diagram is as follows: Suppose that we have already built the Voronoi diagram V_p-1 as shown by solid lines (figure 4.3.1), and would like to add a new sites sp. First, find the site, say s_i, whose Voronoi polygon contains s_p, and draw the perpendicular bisector between s_l and s_i, denoted by B(s_p, s_i). The bisector crosses the boundary of V(s_i) at two points, point x₁ and point x₂. Site sp is to the left of the directed line segment x₁x₂. The line segment x₁x₂ divides the Voronoi polygon V(s_i) into two pieces, the one on the left belonging to the Voronoi polygon of s_p. Thus, we get a Voronoi edge on the boundary of the Voronoi polygon of s_i.

Starting with the edge x₁x₂, expand the boundary of the Voronoi polygon of sl by the following procedure. The B(s_i, s_l) crosses the boundary of V(s_i) at x₂, entering the adjacent Voronoi polygon, say V(s_j). Therefore, next draw the B(s_i, s_j), and find the point, x₃, at which the bisector crosses the boundary of V(s_j). Similarly, find the sequence of segments of perpendicular bisectors of s and the neighboring sites until we reach the starting point x₁. Let this sequence be (x₁x₂, x₂x₃, …, x_m-1x_m, x_mx₁). This sequence forms a counterclockwise boundary of the Voronoi polygon of the new site s. Finally, we delete from Vp-1 the substructure inside the new Voronoi polygon, and thus get V_p.

References

[1]     P. J. Green and R. R. Sibson, Computing Dirichlet tessellations in the plane, Computer Journal vol. 21 n 2 (1978), p.168-173.
[2]     T. Ohya, M. Iri and k. Murota, Improvements of the incremental method for the Voronoi diagram with computational comparison of various algorithms, J. Operational Research Society, Japan 27 (4) (1984), p. 306-336.
[3]     K. Sugihara and M. Iri, Construction of the Voronoi diagram for ‘one million’ sites in single-precision arithmetic, Proc. IEEE 80(9) (1992), 1471-1484.
[4]     J. R. Sack and J. Urrutia, Handbook of Computational Geometry, Elsevier Science B. V. 2000.
[5]     A. Okabe, B. Boots, and K. Sugihara, Spatial Tessellations: Concepts and Applications of Voronoi Diagrams, John Wiley & Sons Ltd, 1992.
[6]     A. Okabe, B. Boots, K. Sugiharan and S. N. Chiu, Spatial Tessellations: Concepts and Applications of Voronoi Diagrams, John Wiley & Sons Ltd, 2002.

Applet