**S**hamos and Hoey [1] presented the first *O(nlogn)* deterministic algorithm for
computing the Voronoi diagram in the plane that is optimal is a worstcase
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

VORONOI_DIAGRAM[3]

INPUT:The numbern> 3 of sites and the listS = (s_{1}, s_{2},. . ., s_{n})of the sites in increasing order of with respect of x-coordinates.OUTPUT:Voronoi diagramVor(S).Step 1 Let

tbe the integral part ofn/2 and split S into= (

S_{L}s_{1},s_{2}, . . . ,s_{t}) andS_{R }= (s_{t+1},s_{t+2}, . . . ,s)._{n}Step 2 Construct the Voronoi diagram

Vor(Sof_{L})Srecursively._{L}Step 3 Construct the Voronoi diagram

Vor(Sof_{R})Srecursively._{R}Step 4 Merge

Vor(Sand_{L})Vor(Sinto the Voronoi diagram of_{R})Vor(S)i.e.,Vor(S)=Vor(SU_{L})Vor(Sby algorithm MERGE_VORONOI._{R})Step 5 Return

Vor(S).

The vital part of algorithm consists of finding the split line, and merging
*Vor(S _{L})*
and

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

MERGE_VORONOI[3]I

NPUT:Voronoi diagramsVor(Sand_{L})Vor(Sof sets_{R})Sand_{L}S._{R}OUTPUT:Voronoi diagrams for set S =SU_{L}S._{R}Step 1 Construct the Convex hull of

Sand_{L}S._{R}

Step 2 Find the lower common support lineL(S,_{L}S) by Algorithm LOWER_COMMON_SUPPORT._{R}

Step 3 w_{o}← the point at infinity downward on perpendicular bisector of sitessand_{l}belongs to S_{L}s. i.e.,_{R}belongs to S_{R}B(S,_{L}S)._{R}i← 0

Step 4 WhileL(S,_{L}S) is not the upper support_{R}

Repeat

4.1i←i+ 1

4.2 Find the intersection point ofB(S,_{L}S) with the boundary of_{R}V(s, say a_{L})_{L}.

4.3 Find the intersection point ofB(S,_{L}S) with the boundary of_{R}V(s, say a_{R})_{R}.

4.4 IF yvalue of a L is smaller that yvalue of a_{R}.

THEN

w← a_{i }_{L}

s← sites on the other side of the Voronoi edge containing a_{L}_{L}.

ELSE

w← a_{i }_{R}

s← the site on the other side of the Voronoi edge containing a_{R}_{R}.

Step 5m←i.W← the point at infinity upward on the perpendicular bisector of_{m+1 }sand_{l}belongs to S_{L}s. i.e.,_{R}belongs to S_{R}B(S,_{L}S)._{R}

Step 6 Add the polygonal line (w0w1,w1w2, . . . ,w_{m}w_{m+1}), and delete fromVorthe 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._{L}

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 polygonPand_{L}Psuch that_{R}Pis completely left of_{L}P._{R}A pair consisting of vertex

OUTPUT:u belongs toPand_{L}v belongs toPsuch that_{R}L(u, v)forms the lower common support of polygonsPand_{L}P._{R}Step 1 Find the vertex

u belongs toPwith the largest x coordinate and the_{L}v belongs toPwith the smallest_{R}xcoordinate.

Step 2 Repeat substeps 2.1 and 2.2 Alternately.2.1 While vertex next[

u] is lower thanL(u, v)

Repeatu← next[u].

2.2 While vertex next[v] is lower thanL(u, v)

Repeatv← 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 quadedge data structure. Dwyer's implementation [5]
apply
vertical and horizontal split lines in turn. Katajainen and Koppinen's [6]
merge
square buckets in a quadtree order [7, 8]. It is worthy to note that divide-and-conquer algorithms are also excellent candidates for efficient parallelization.

**Divide-and-Conquer Voronoi Diagram Applet**

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