Voronoi diagram algorithms

The complete solution

Finds the Voronoi diagram for n given points. n can be 0. Assumes no duplicates. for each point P_k, 1≤k≤n find the perpendicular bisectors B_m, 1≤m≤n add the screen edge "bisectors" B_m, n+1≤m≤n+4 for each intersection point T_i,j of the bisectors, k+1≤i<n+4, i<j≤n+4 if the line segment through T_i,j and P_k does not intersect any B_m, k+1≤m≤n, m≠i,j add T_i,j to P_k's polygon if i≤n, add T_i,j to P_i's polygon if j≤n, add T_i,j to P_j's polygon

The incremental solution

Finds the Voronoi diagram after adding a new point. Differs only slightly, as marked, from the complete solution. to add a new point P_k, n<-n+1, k=n find the perpendicular bisectors B_m, 1≤m≤n add the screen edge "bisectors" B_m, n+1≤m≤n+4 for each point P_r, 1≤r<n remove each point from P_r's polygon that lies on the opposite side of B_r from P_r for each intersection point T_i,j of the bisectors, 1≤i<n+4, i<j≤n+4 if the line segment through T_i,j and P_k does not intersect any B_m, 1≤m≤n, m≠i,j add T_i,j to P_k's polygon if i≤n, add T_i,j to P_i's polygon if j≤n, add T_i,j to P_j's polygon