FINDING CONGRUENT REGIONS IN PARALLEL

被引：5

作者：

BOXER, L

机构：

[1] Department of Computer and Information Sciences, Niagara University

来源：

PARALLEL COMPUTING | 1992年 / 18卷 / 07期

关键词：

SYSTOLIC ARRAY ALGORITHM; FINDING CONGRUENT REGIONS; CREW PRAM; TIMING ANALYSIS;

D O I：

10.1016/0167-8191(92)90046-A

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Given a straight-line embedded plane graph G of n edges and a polygon P of m edges, m less-than-or-equal-to n, we describe an algorithm for finding all polygons in G that are congruent to P. Our algorithm requires THETA(n log n) time for a CREW PRAM with m processors. This improves upon the O(n2) time (with m processors) required by the systolic array algorithm of [7]. We also show the problem is in NC by showing how to implement our algorithm in THETA(log n) time using mn processors.

引用

页码：807 / 810

页数：4

共 7 条

[1]

Ballard DH, 1982, COMPUTER VISION

[2]

BOXER L, 1990, 7TH P ISR C ART INT, P325

[3] PARALLEL MERGE SORT [J].

COLE, R .

SIAM JOURNAL ON COMPUTING, 1988, 17 (04) :770-785

[4]

DIRILTEN H, 1977, IEEE T COMPUT, V26, P314, DOI 10.1109/TC.1977.1674832

[5] TIME-SPACE OPTIMAL PARALLEL MERGING AND SORTING [J].

GUAN, XJ ;

LANGSTON, MA .

IEEE TRANSACTIONS ON COMPUTERS, 1991, 40 (05) :596-602

[6]

KRUSKAL CP, 1985, 1985 P INT C PAR PRO, P180

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

SHIH, ZC ;

LEE, RCT ;

YANG, SN .

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

← 1 →