PARALLEL VORONOI DIAGRAM IN L1 (LINFINITY) METRIC ON A MESH-CONNECTED COMPUTER

被引：3

作者：

JEONG, CS

机构：

[1] Department of Computer Science, Pohang Institute of Science and Technology, P.O. BOX 125

来源：

PARALLEL COMPUTING | 1991年 / 17卷 / 2-3期

关键词：

PARALLEL ALGORITHM; VORONOI DIAGRAM; MESH-CONNECTED COMPUTER;

D O I：

10.1016/S0167-8191(05)80109-7

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

In this paper, we consider the problem of constructing a Voronoi diagram in L1(L-infinity) metric for a set of n points in the Cartesian plane on a mesh-connected computer. An O(square-root n) parellel algorithm on a square-root n x square-root n mesh-connected computer is given for solving that problem. This is the first solution on a square-root n x square-root n MCC to achieve an asymptotically optimal theta(square-root n) running time for L1(L-infinity) metric.

引用

页码：241 / 252

页数：12

共 12 条

[1] Aggarwal A., 1985, 26th Annual Symposium on Foundations of Computer Science (Cat. No.85CH2224-4), P468, DOI 10.1109/SFCS.1985.42
[2] VORONOI DIAGRAMS FROM CONVEX HULLS
BROWN, KQ
[J]. INFORMATION PROCESSING LETTERS, 1979, 9 (05) : 223 - 228
[3] CHOW AL, 1980, THESIS U ILLINIS URB
[4] O(N LOG N) ALGORITHM FOR RECTILINEAR MINIMAL SPANNING TREES
HWANG, FK
[J]. JOURNAL OF THE ACM, 1979, 26 (02) : 177 - 182
[5] JEONG CS, 1990, ALGORITHMICA, V5, P155, DOI 10.1007/BF01840383
[6] JEONG CS, 1987, FJCC, P560
[7] 2-DIMENSIONAL VORONOI DIAGRAMS IN THE LP-METRIC
LEE, DT
[J]. JOURNAL OF THE ACM, 1980, 27 (04) : 604 - 618
[8] VORONOI DIAGRAMS IN L1 (L INFINITY) METRICS WITH TWO-DIMENSIONAL STORAGE APPLICATIONS
LEE, DT
WONG, CK
[J]. SIAM JOURNAL ON COMPUTING, 1980, 9 (01) : 200 - 211
[9] LU M, 1986, 1986 P INT C PAR PRO, P806
[10] DATA-BROADCASTING IN SIMD COMPUTERS
NASSIMI, D
SAHNI, S
[J]. IEEE TRANSACTIONS ON COMPUTERS, 1981, 30 (02) : 101 - 107

← 1 2 →