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 [J].