AN OPTIMAL PARALLEL ALGORITHM FOR DETECTING WEAK VISIBILITY OF A SIMPLE POLYGON

被引：11

作者：

CHEN, DZ ^{[1
]}

机构：

[1] UNIV NOTRE DAME,DEPT COMP SCI & ENGN,NOTRE DAME,IN 46556

来源：

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS | 1995年 / 5卷 / 1-2期

关键词：

COMPUTATIONAL GEOMETRY; CREW PRAM; PARALLEL ALGORITHMS; SIMPLE POLYGONS; WEAK VISIBILITY;

D O I：

10.1142/S0218195995000076

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

The problem of detecting the weak visibility of an n-vertex simple polygon P is that of finding whether P is weakly visible from one of its edges and (if it is) identifying every edge from which P is weakly visible. In this paper, we present an optimal parallel algorithm for solving this problem. Our algorithm runs in O (log n) time using O (n/log n) processors in the CREW PRAM computational model, and is very different from the sequential algorithms for this problem. Based on this algorithm, several other problems related to weak visibility can be optimally solved in parallel.

引用

页码：93 / 124

页数：32

共 30 条

[1]

ATALLAH MJ, 1991, J ACM, V38, P516, DOI 10.1145/116825.116827

[2]

AVIS D, 1981, IEEE T COMPUT, V30, P910, DOI 10.1109/TC.1981.1675729

[3]

BHATTACHARYA BK, 1989, 5TH P ACM S COMP GEO, P247

[4]

BHATTACHARYA BK, 1991, 1991 P WORKSH ALG DA, P412

[5] VISIBILITY AND INTERSECTION PROBLEMS IN PLANE GEOMETRY [J].

CHAZELLE, B ;

GUIBAS, LJ .

DISCRETE & COMPUTATIONAL GEOMETRY, 1989, 4 (06) :551-581

[6]

CHEN DZ, 1993, IN PRESS 4TH ANN INT

[7]

CHEN DZ, 1990, 28TH P ALL C COMM CO, P818

[8]

CHEN DZ, 1992, NPUB 8TH P ANN ACM S, P63

[9]

CHEN DZ, 1992, 92051 PURD U DEP COM

[10]

CHING YT, 1989, CRUISING GUARD PROBL

← 1 2 3 →