Algorithm 1:Divide-and-conquer method

Input: Number n of generators and list P={ p₁,…,p_n } of the generators arranged in increasing order of the x coordinates.

Output: Voronoi diagram V for P.

Procedure:

Step1. If n≤3, then construct the Voronoi diagram V for P directly and go to Step3.

Step2. Otherweise do the following.

     2.1. Let t be the integral part of n/2, and divide P into P_L={ p₁,…,p_t } and P_R={ p_t+1,…,p_n }.

     2.2. Construct the Voronoi diagram V_L for P_L by algorithm 2.

     2.3. Construct the Voronoi diagram V_R for P_R by algorithm 2.

     2.4. Merge V_L and V_R into the Voronoi diagram V for P(it can be done by Algorithm 2）。

Step3. Return V.

Algorithm 2:Merge of two Voronoi diagrams

Input: Two Voronoi diagrams V_L and V_R for generators sets P_L and P_R , respectively, such that the generators in V_L have smaller x coordinates than those in V_R .

Output: Voronoi diagram for P_LP_R

Procedure:

Step1. Construct the convex hull of P_L and that of P_R .

Step2. Find the lower common support L(P_L, P_R).

Step3. w₀←the point at infinity downward on b(P_L, P_R),and i←0.

Step4. while L(P_L, P_R) is not the upper common support, repeat 4.1,…,4.4.

          4.1 i ←i+1.

4.2. Find the point a_L(other than wi-1) of the intersection of b(P_L, P_R) with the boundary of V(P_L).

4.3. Find the point a_R(other than wi-1) of the intersection of b(P_L, P_R) with the boundary of V(P_R).

4.4. If has a_L smaller y coordinate than ,

w_i←a_L, and

P_L←the generator on the other side of the Voronoi edge containing a_L.

Otherwise

w_i←a_R, and

P_R←the generator on the other side of the Voronoi edge containing a_R.

Step5. m←i.

W_m+1←the point at infinity upward on b(P_L, P_R).

Step6. Add the polygonal line(w₀w₁,w₁w₂,…,w_mw_m+1),and delete from V_L the part to the right of the polygonal line. Return the resultant diagram.