TESTING A SIMPLE POLYGON FOR MONOTONICITY OPTIMALLY IN PARALLEL

被引：3

作者：

CHEN, DZ

GUHA, S

机构：

[1] UNIV WISCONSIN,DEPT ELECT ENGN & COMP SCI,MILWAUKEE,WI 53201

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

来源：

INFORMATION PROCESSING LETTERS | 1993年 / 47卷 / 06期

基金：

美国国家科学基金会;

关键词：

PARALLEL ALGORITHMS; COMPUTATIONAL GEOMETRY; SIMPLE POLYGONS;

D O I：

10.1016/0020-0190(93)90080-S

中图分类号：

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

学科分类号：

0812 ;

摘要：

We show that, in parallel, an n-vertex simple polygon can be tested for monotonicity optimally in 0(log n) time using 0(n/log n) EREW PRAM processors, and we present two different optimal parallel algorithms for solving this problem. Our result leads to an optimal parallel algorithm for triangulating simple polygons that runs in 0(log;n) time using 0(n/log n) EREW PRAM processors if the polygons are monotone.

引用

页码：325 / 331

页数：7

共 18 条

[1] AN OPTIMAL PARALLEL ALGORITHM FOR THE MINIMUM CIRCLE-COVER PROBLEM [J].