 ## Voronoi Diagram using Shamos and Hoey  presented the first O(nlogn) deterministic algorithm for computing the Voronoi diagram in the plane that is optimal is a worstŁcase sense. This algorithm is significant from a theoretical standpoint not only because it was the first one but also it uses the divide-and-conquer paradigm. The 'Divide-and-Conquer' is one of the fundamental paradigms for designing efficient algorithms. In this paradigm, the original problem is recursively divided into several simpler sub-problems of roughly equal size, and the solution of the original problem obtained by merging the solutions of the sub-problems. In the divide-and-conquer approach of  Shamos and Hoey, the set of sites, S, is split up by a dividing line into subsets SL and SR of about same sizes. Then, the Voronoi diagram, Vor(SL), of  subset SL and Voronoi diagram, Vor(SR), of  subset SR are computed recursively .  VORONOI_DIAGRAM 

INPUT:     The number n > 3 of sites and the list S = (s1 , s2 , . . . , sn) of the sites in increasing order of with respect of x-coordinates.
OUTPUT: Voronoi diagram Vor(S).

Step 1  Let t be the integral part of n/2 and split S into
SL
= (s1 , s2 , . . . , st) and SR = (st+1 , st+2 , . . . , sn).

Step 2  Construct the Voronoi diagram Vor(SL) of SL recursively.

Step 3  Construct the Voronoi diagram Vor(SR) of SR recursively.

Step 4  Merge Vor(SL) and Vor(SR) into the Voronoi diagram of Vor(S) i.e., Vor(S)Vor(SL) U Vor(SR) by algorithm MERGE_VORONOI.

Step 5 Return Vor(S).

The vital part of algorithm consists of finding the split line, and merging Vor(SL) and Vor(SR), to obtain Vor(S) of original set S. If computing the split line and merging of two Voronoi diagrams could carried out in time O(n) then the overall running time is O(n log n) from the recurrence relation T(n) = 2T (n/2) + O(n).

Calculation of vertical or horizontal split lines is straightforward during recursion if the sites in S are sorted by their x and y coordinates beforehand. Any optimal sorting algorithm such as a heap sort or a merge sort  does this task in O(n log n) time.

Merging Voronoi Diagrams

The merge step involves computing the set of perpendicular bisector s of sets SL and SR i.e., B(SL , SR ), of all Voronoi edges of Vor(S) that separates the sites in SL from regions of sites in SR. The idea of merging based on the fact that the edges of B(SL , SR) form a single y-monotone polygonal chain. This can be proved by taking any edge b of B(SL , SR) and two sites l belongs to L and r belongs to R of two regions adjacent to b. The smaller xŁcoordinate of  l with respect to xŁcoordinate of r implies that b cannot be horizontal. Thus, stitch together the part of V(SL) to the left of  B(SL , SR) with the part of V(SR) to the right of  B(SL , SR) to get V(S). Find a starting edge at infinity, and by tracing  B(SL , SR) through V(SL) and V(SR) in order to construct the polygonal chain B(SL , SR). The time O(n) to find the starting edge at infinity by determining a line tangent to the convex hulls of SL and SR, respectively is due to Shamos and Hoey . Algorithm MERGE_VORONOI represents this idea. In total MERGE_VORONOI runs in O(n) time since, steps 1 and 6 are done in O(n) time, step 2 is done in O(n) time by algorithm SUPPORT, step 3 and 5 in constant time and step 4 is repeated at most O(n) times.

MERGE_VORONOI 

INPUT:      Voronoi diagrams Vor(SL) and Vor(SR) of sets SL and SR .
OUTPUT:  Voronoi diagrams for set S = SL U SR .

Step 1  Construct the Convex hull of SL and SR.
Step 2  Find the lower common support line L(SL , SR) by Algorithm LOWER_COMMON_SUPPORT.
Step 3  wo the point at infinity downward on perpendicular bisector of sites sl belongs to SL and sR belongs to SR . i.e.,  B(SL , SR). i 0
Step 4  While L(SL , SR) is not the upper support
Repeat
4.1                 i   i + 1
4.2                 Find the intersection point of B(SL, SR) with the boundary of V(sL), say aL .
4.3                 Find the intersection point of B(SL, SR)  with the boundary of V(sR), say aR .
4.4                 IF yŁvalue of a L is smaller that yŁvalue of aR.
THEN
wi   aL
sL  ← sites on the other side of the Voronoi edge containing aL .
ELSE
wi aR
sR the site on the other side of the Voronoi edge containing aR.
Step 5  m i. Wm+1  the point at infinity upward on the perpendicular bisector of sl belongs to SL and sR belongs to SR . i.e.,  B(SL , SR).
Step 6  Add the polygonal line (w0w1 , w1w2 , . . . , w_{m}w_{m+1}), and delete from VorL the part to the right of the polygonal line and delete from Vor R from the part to the left polygonal line. Return the resultant Voronoi diagram.

Support line Computation

The algorithm MERGE_VORONOI involves convex polygons and calculation of common support line and presented in algorithm LOWER_COMMON_SUPPORT. The algorithm runs in O(n) time. In fact there is an O(log n) algorithm for finding the common support by Overmars and Leevwen . But since this sub-problem is not a bottleneck of the total time complexity, following O(n) algorithm is quite enough.

LOWER_COMMON_SUPPORT 

INPUT :      Two Convex polygon PL and PR such that PL is completely left of PR .
OUTPUT:
A pair consisting of vertex u belongs to PL and v belongs to PR  such that L(u, v) forms the lower common support of polygons PL  and PR.

Step 1    Find the vertex u belongs to PL  with the largest x coordinate and the  v belongs to PR  with the smallest x coordinate.
Step 2    Repeat subŁsteps 2.1 and 2.2 Alternately.

2.1      While vertex next[u] is lower than L(u, v)
Repeat u next[u].
2.2      While vertex next[v] is lower than L(u, v)
Repeat v next[v].

Step 3    Return L(u, v).

The above description of an algorithm VORONOI_DIAGRAM leads to the following conclusion. In the worst case, O(n log n) time and linear space is requires to construct the Voronoi diagram of n sites in the plane using the divide-and-conquer paradigm. Note that both bounds are optimal. There are many variation to this classical divide-and-conquer approach presented by Shamos and Hoey . For example, Guibas and Stolfi  provide an implementation that utilize the quadŁedge data structure. Dwyer's implementation  apply vertical and horizontal split lines in turn. Katajainen and Koppinen's  merge square buckets in a quadŁtree order [7, 8]. It is worthy to note that divide-and-conquer algorithms are also excellent candidates for efficient parallelization.

## Construction of Dividing Chain

### Step 1 ## Step 2 ### Step 3 ### Step 4 ### Step 5 ### Step 6 ### Step 7 ### Step 8 ### Step 9 ### Step 10 ### Step 11 ### Step 12 ### Step 13 ### Step 14 ### Step 15 ### Step 16 ### Step 17 Divide-and-Conquer Voronoi Diagram Applet

If you see no Applet here...
... Enable your browser with JAVA!

## Reference

     M. I. Shamos and D. Hoey, Closest-point problems, Proc. 16th Annu. IEEE Sympos. Foind. Comput. Sci. (1975), 151-162.

     L. J. Guibas and J. Stolfi, Primitives for the manipulation of general subdivisions and the computions of Voronoi diagrams, ACM Trans. Graph. 4 (1985), 74-123.

     A. Okabe, B. Boots, and K. Sugihara, Spatial Tessellations, Concepts and Applications of Voronoi diagrams, John Wiley & Sons Ltd. England (1992)

     J. R. Sack and J. Urrutia, Handbook of Computational Geometry, Elsevier Science, Netherlands (2000)

     R. A. Dwyer, A faster divide-and-conquer algorithm for constructing Delaunay triangulations, Algorithmica 2 (1987), 137-151.

     J. Katajainen and M. Koppinen, Constructing Delaunay triangulations by merging buckets in quad order, Ann. Soc. Math. Polon. series IV, Fund. Inform. 11 (3) (1988), 275-288.

     H. Samet, The Design and Analysis of Spatial Data Structures, Addison-Wesley, Reading, MA (1990).

     H. Samet, Applications of Spatial Data Structures, Addison-Wesley, Reading, MA (1990).

     A. Gibbons, Algorithmic Graph Theory, Cambridge University Press, Cambridge (1985).

   Donald E. Knuth, The Art of Programming Languages, Reading Mass,.: Addison Wesley, 1981.

   M. H. Overmars and J. van Leeuwen, Maintainance of point configurations in the plane, J. of Computers and System Sciences, 23, p. 116-204. 