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(n2). 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 Vp denoted the Voronoi diagram for the first p sites s1, s2, . . . , sp. The major part of the incremental method is to translate Vp-1 to Vp for each p.

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

Starting with the edge x1x2, expand the boundary of the Voronoi polygon of sl by the following procedure. The B(si, sl) crosses the boundary of V(si) at x2, entering the adjacent Voronoi polygon, say V(sj). Therefore, next draw the B(si, sj), and find the point, x3, at which the bisector crosses the boundary of V(sj). Similarly, find the sequence of segments of perpendicular bisectors of s and the neighboring sites until we reach the starting point x1. Let this sequence be (x1x2, x2x3, …, xm-1xm, xmx1). 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 Vp.





[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.