Shamos and Hoey [1] 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 S_L and S_R of about same sizes. Then, the Voronoi diagram, Vor(S_L), of  subset S_L and Voronoi diagram, Vor(S_R), of  subset S_R are computed recursively [4].

 

 

VORONOI_DIAGRAM [3]

INPUT:     The number n > 3 of sites and the list S = (s₁ , s₂ , . . . , s_n) 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
            S_L = (s₁ , s₂ , . . . , s_t) and S_R = (s_t+1 , s_t+2 , . . . , s_n).

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

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

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

Step 5 Return Vor(S).

The vital part of algorithm consists of finding the split line, and merging Vor(S_L) and Vor(S_R), 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 [10] 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 S_L and S_R i.e., B(S_L , S_R ), of all Voronoi edges of Vor(S) that separates the sites in S_L from regions of sites in S_R. The idea of merging based on the fact that the edges of B(S_L , S_R) form a single y-monotone polygonal chain. This can be proved by taking any edge b of B(S_L , S_R) 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(S_L) to the left of  B(S_L , S_R) with the part of V(S_R) to the right of  B(S_L , S_R) to get V(S). Find a starting edge at infinity, and by tracing  B(S_L , S_R) through V(S_L) and V(S_R) in order to construct the polygonal chain B(S_L , S_R). The time O(n) to find the starting edge at infinity by determining a line tangent to the convex hulls of S_L and S_R, respectively is due to Shamos and Hoey [1]. 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 [3]

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

Step 1  Construct the Convex hull of S_L and S_R.
Step 2  Find the lower common support line L(S_L , S_R) by Algorithm LOWER_COMMON_SUPPORT.
Step 3  w_o ← the point at infinity downward on perpendicular bisector of sites s_l belongs to S_L and s_R belongs to S_R . i.e.,  B(S_L , S_R). i ← 0
Step 4  While L(S_L , S_R) is not the upper support
            Repeat
4.1                 i ←  i + 1
4.2                 Find the intersection point of B(S_L, S_R) with the boundary of V(s_L), say a_L .
4.3                 Find the intersection point of B(S_L, S_R)  with the boundary of V(s_R), say a_R .
4.4                 IF y­value of a L is smaller that y­value of a_R.
                            THEN
                                     w_i  ← a_L
                                     s_L  ← sites on the other side of the Voronoi edge containing a_L .
                            ELSE
                                    w_i ← a_R
                                    s_R ← the site on the other side of the Voronoi edge containing a_R.
Step 5  m ← i. W_m+1 ←  the point at infinity upward on the perpendicular bisector of s_l belongs to S_L and s_R belongs to S_R . i.e.,  B(S_L , S_R).
Step 6  Add the polygonal line (w0w1 , w1w2 , . . . , w_{m}w_{m+1}), and delete from Vor_L 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 [11]. But since this sub-problem is not a bottleneck of the total time complexity, following O(n) algorithm is quite enough.

LOWER_COMMON_SUPPORT [3]

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

Step 1    Find the vertex u belongs to P_L  with the largest x coordinate and the  v belongs to P_R  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 [1]. For example, Guibas and Stolfi [2] provide an implementation that utilize the quad­edge data structure. Dwyer's implementation [5] apply vertical and horizontal split lines in turn. Katajainen and Koppinen's [6] 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

The most important part in the game of Voronoi construction is to construct the dividing chain (polygonal line, polygonal chain, split line, and so on). So, lets construct dividing chain step-by-step.

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

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

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

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

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

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

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

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

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

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

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

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