A PARALLEL ALGORITHM FOR FINDING CONGRUENT REGIONS

被引：4

作者：

LEI, CL

LIAW, HT

机构：

[1] Department of Electrical Engineering, National Taiwan University, Taipei

来源：

COMPUTERS & GRAPHICS | 1992年 / 16卷 / 03期

关键词：

D O I：

10.1016/0097-8493(92)90006-H

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

In this paper, we study the problem for finding all the regions, which are congruent to a testing region R, in an input planar figure F. In a shared memory system with m processors, we propose an efficient MAX {O(mn), O(n log n)} time parallel algorithm, where n, m are the numbers of edges of F and R, respectively. Furthermore, our algorithm does not require to read from or write into the same memory location simultaneously, hence it can be implemented on an exclusive-read, exclusive-write (EREW) model.

引用

页码：289 / 294

页数：6

共 10 条

[1]

AKL AG, 1978, INF P LETT, V7, P127

[2]

ALT H, 1987, 3RD P ANN S COMP GEO, P308

[3]

[Anonymous], [No title captured]

[4] CHECKING SIMILARITY OF PLANAR FIGURES [J].

ATALLAH, MJ .

INTERNATIONAL JOURNAL OF COMPUTER & INFORMATION SCIENCES, 1984, 13 (04) :279-290

[5] AN OPTIMAL ALGORITHM FOR GEOMETRICAL CONGRUENCE [J].

ATKINSON, MD .

JOURNAL OF ALGORITHMS, 1987, 8 (02) :159-172

[6]

BAUDET G, 1978, IEEE T COMPUT, V27, P84, DOI 10.1109/TC.1978.1674957

[7] POLYGON SIMILARITY [J].

BYKAT, A .

INFORMATION PROCESSING LETTERS, 1979, 9 (01) :23-25

[8]

Knuth D.E., 1997, ART COMPUTER PROGRAM, V3

[9] A PARALLEL ALGORITHM FOR FINDING CONGRUENT REGIONS [J].

SHIH, ZC ;

LEE, RCT ;

YANG, SN .

PARALLEL COMPUTING, 1990, 13 (02) :135-142

[10] AN N LOG N ALGORITHM FOR DETERMINING THE CONGRUITY OF POLYHEDRA [J].

SUGIHARA, K .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1984, 29 (01) :36-47

← 1 →