TIME-OPTIMAL AND VLSI-OPTIMAL CONVEX-HULL COMPUTATION ON MESHES WITH MULTIPLE BROADCASTING

被引：2

作者：

BOKKA, V ^{[1
]}

GURLA, H ^{[1
]}

OLARIU, S ^{[1
]}

SCHWING, JL ^{[1
]}

机构：

[1] OLD DOMINION UNIV,DEPT COMP SCI,NORFOLK,VA 23529

来源：

INFORMATION PROCESSING LETTERS | 1995年 / 56卷 / 05期

基金：

美国国家科学基金会; 美国国家航空航天局;

关键词：

COMPUTATIONAL GEOMETRY; PARALLEL ALGORITHMS; DESIGN OF ALGORITHMS; COMPUTER ARCHITECTURE;

D O I：

10.1016/0020-0190(95)00160-8

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

Our main contribution is to present the first known general-case, time- and VLSI-optimal, algorithm for convex hull computation on meshes with multiple broadcasting. Specifically, we show that for every choice of a positive constant epsilon, the convex hull of a set of an arbitrary set of m (n(1/2+epsilon) less than or equal to m less than or equal to n) points in the plane input in the first [m/root n] columns of a mesh with multiple broadcasting of size root n x root n can be computed in Theta(m/root n) time.

引用

页码：273 / 280

页数：8

共 23 条

[1] PARALLEL ALGORITHMS FOR SOME FUNCTIONS OF 2 CONVEX POLYGONS [J].

ATALLAH, MJ ;

GOODRICH, MT .

ALGORITHMICA, 1988, 3 (04) :535-548

[2] SQUARE MESHES ARE NOT ALWAYS OPTIMAL [J].

BARNOY, A ;

PELEG, D .

IEEE TRANSACTIONS ON COMPUTERS, 1991, 40 (02) :196-204

[3]

BHAGAVATHI D, 1993, PROC INT CONF PARAL, P307

[4] A FAST SELECTION ALGORITHM FOR MESHES WITH MULTIPLE BROADCASTING [J].

BHAGAVATHI, D ;

LOOGES, PJ ;

OLARIU, S ;

SCHWING, JL ;

ZHANG, J .

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 1994, 5 (07) :772-778

[5]

Bhagavathi D., 1992, Parallel Processing Letters, V2, P249, DOI 10.1142/S0129626492000386

[6] A TIME-OPTIMAL MULTIPLE SEARCH ALGORITHM ON ENHANCED MESHES, WITH APPLICATIONS [J].

BHAGAVATHI, D ;

OLARIU, S ;

SHEN, W ;

WILSON, L .

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 1994, 22 (01) :113-120

[7]

BHAGAVATHI D, 1993, P INT C PAR PROC ST, P196

[8]

CHAZELLE B, 1984, IEEE T COMPUT, V33, P774, DOI 10.1109/TC.1984.1676494

[9]

Chen Y.-C., 1990, IEEE Transactions on Parallel and Distributed Systems, V1, P241, DOI 10.1109/71.80135

[10]

HOLEY JA, 1990, P INT C PARALLEL PRO, P147

← 1 2 3 →