##

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*^{2}). 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*_{1}, *s*_{2}, . . . , *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*_{1} and point *x*_{2}. Site sp is to the left of the directed line
segment *x*_{1}*x*_{2}. The line segment *x*_{1}*x*_{2} 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*_{1}*x*_{2}, 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*_{2},
entering the adjacent Voronoi polygon, say *V*(*s*_{j}). Therefore, next draw the
*B*(*s*_{i},
*s*_{j}), and find the point, *x*_{3}, 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*_{1}. Let this sequence be
(*x*_{1}*x*_{2}, *x*_{2}*x*_{3}, …,* x*_{m-1}*x*_{m},
*x*_{m}x_{1}). 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