An improved parallel algorithm for construction Voronoi diagram ona mesh-connected computer

摘要

While constructing a Voronoi diagram V_p for aset P of n points on a mesh-connected computer(MCC),it is necessary to find a set B of edges which are intersectedby the dividing chain C during the merge process of two Voronoidiagrams V_L and V_A, where L and R contain the leftmost [n/2] points and therightmost [n/2] points of P respectively. Thecomputation of B requires two operations: First decide for eachedge e in V_L and V_Rwhether its end vertices are closer to L or R, andthen from that information, determine, whether e is intersectedby C. The paper shows that the latter operation can be done inO(1) time without executing planar point location and the formeroperation can be executed without the computation of convex hulls.Therefore, the computation of B is reduced to only one planarpoint location