AN IMPROVED PARALLEL ALGORITHM FOR CONSTRUCTING VORONOI DIAGRAM ON A MESH-CONNECTED COMPUTER

被引:6
作者
JEONG, CS
机构
[1] Department of Computer Science, Pohang Institute of Science and Technology, P.O. Box 125
关键词
PARALLEL ALGORITHM; VORONOI DIAGRAM; MESH-CONNECTED COMPUTER;
D O I
10.1016/S0167-8191(05)80152-8
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
While constructing a Voronoi diagram V(P) for a set of P of n points on a mesh-connected computer (MCC), it is necessary to find a set B of edges which are intersected by the dividing chain C during the merge process of two Voronoi diagrams V(L) and V(R), where L and R contain the leftmost [n/2] points and the rightmost [n/2] points of P respectively. The computation of B requires two operations: First decide for each edge e in V(L) and V(R) whether its end vertices are closer to L or R, and then from that information, determine whether e is intersected by C. However, in the previous parallel algorithm each of the former and latter operations requires planar point location which takes O(square-root n) time on square-root n x square-root n MCC, and in addition the former operation needs to compute convex hulls of L and R. In this paper, we shall show that the latter operation can be done in O(1) time without executing planar point location and the former operation can be executed without the computation of convex hulls. Therefore, the computation of B is reduced to only one planar point location.
引用
收藏
页码:505 / 514
页数:10
相关论文
共 7 条
[1]  
Aggarwal A., 1985, 26th Annual Symposium on Foundations of Computer Science (Cat. No.85CH2224-4), P468, DOI 10.1109/SFCS.1985.42
[2]  
Chow A., 1980, THESIS U ILLINOIS UR
[3]  
EVANS DJ, 1989, PARALLEL COMPUT, P121
[4]  
JEONG CS, 1990, ALGORITHMICA, V5, P155, DOI 10.1007/BF01840383
[5]  
JEONG CS, 1987, FJCC, P560
[6]  
Preparata F.P., 1985, COMPUTATIONAL GEOMET, DOI [10.1007/978-1-4612-1098-6, DOI 10.1007/978-1-4612-1098-6]
[7]  
SHAMOS MI, 1975, 16TH P S F COMP SCI, P152