Algorithm :Quaternary incremental method

Input: Set{ p₄, p₅,…,p_n } of n-3 generators located in the unit square S={(x,y)| 0≤x,y≤1}.

Output: Voronoi diagram V for n generators{ p₁,…,p_n },where p₁, p₂ and p₃ are the additional generators defined by system that won’t impact the final result.

Procedure:

Step1.   Find positive integer k such that 4^k is closest to n, divide S into 4^k square buckets, and construct the quaternary tree having the buckets as leaves.

Step2.   Renumber the generators by the quaternary reordering, and let the resultant order be p₄, p₅,…,p_n.

Step3.   Construct the Voronoi diagram V₃ for the three additional generators p₁, p₂ and p₃ .

Step4.   For l=4,5,…,n do 4.1,..4.4.

4.1. By nearest neighbour search algorithm with the initial guess given by the quaternary initial guessing, find the generator pi (1≤i≤l-1) closest to p_l.

4.2. find the points w1 and w2 of intersection of the perpendicular bisector of p_i and p_l with the boundary of V(P_i).

4.3. By the boundary growing procedure, construct the closed sequence of segments of perpendicular bisectors forming the boundary of the Voronoi polygon of P_l.

4.4. Delete from V_l-1 the substructure inside the closed sequence,and name the resultant diagram V_l.

Step5 Return V=V_n.