EFFICIENT VLSI PARALLEL ALGORITHM FOR DELAUNAY TRIANGULATION ON ORTHOGONAL TREE NETWORK IN 2-DIMENSIONS AND 3-DIMENSIONS

被引：9

作者：

SAXENA, S ^{[1
]}

BHATT, PCP ^{[1
]}

PRASAD, VC ^{[1
]}

机构：

[1] INDIAN INST TECHNOL, DEPT ELECT ENGN, NEW DELHI 110016, INDIA

来源：

IEEE TRANSACTIONS ON COMPUTERS | 1990年 / 39卷 / 03期

关键词：

Algorithms; computational geometry; Delaunay triangulation; orthogonal tree network; parallel computing; Thompson's model; VLSI complexity;

D O I：

10.1109/12.48871

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

In this correspondence, a parallel algorithm for two and three-dimensional Delaunay triangulation on an orthogonal tree network is described. The worst case time complexity of this algorithm is O(log2 N) in two dimensions and O(m1/2 log N) in three dimensions with N input points and m as the number of tetrahedra in triangulation. The AT2 VLSI complexity on Thompson's logarithmic delay model is O(N2 log6 N) in two dimensions and O(m2N log4 N) in three dimensions. © 1990 IEEE

引用

页码：400 / 404

页数：5

共 19 条

[1]

AGGARWAL A, 1987, PARALLAL COMPUTATION

[2]

ATALLAH MJ, 1987, CASCADING DIVIDE CON

[3] GEOMETRIC STRUCTURES FOR 3-DIMENSIONAL SHAPE REPRESENTATION [J].

BOISSONNAT, JD .

ACM TRANSACTIONS ON GRAPHICS, 1984, 3 (04) :266-286

[4]

Cavendish J. C., 1974, International Journal for Numerical Methods in Engineering, V8, P679, DOI 10.1002/nme.1620080402

[5] AN O(N LOG N) MINIMAL SPANNING TREE ALGORITHM FOR N-POINTS IN THE PLANE [J].

CHANG, RC ;

LEE, RCT .

BIT, 1986, 26 (01) :7-16

[6]

CHOW A, 1980, THESIS U ILLINOIS UR

[7]

DADOUN D, 1987, P ACM S COMPUTATIONA, P205

[8]

EDELSBRUNER H, 1987, ALGORITHMS COMBINATO

[9]

FIELD DA, 1986, P 2 ANN S COMP GEOM, P246

[10] PRIMITIVES FOR THE MANIPULATION OF GENERAL SUBDIVISIONS AND THE COMPUTATION OF VORONOI DIAGRAMS [J].

GUIBAS, L ;

STOLFI, J .

ACM TRANSACTIONS ON GRAPHICS, 1985, 4 (02) :74-123

← 1 2 →