A PARALLEL ALGORITHM FOR ENCLOSED AND ENCLOSING TRIANGLES

被引：31

作者：

Chandran, Sharat ^{[1
]}

Mountt, David M. ^{[2
,3
]}

机构：

[1] NTT Data Commun Syst Corp, Saiwai Ku, Kawasaki, Kanagawa 210, Japan

[2] Univ Maryland, Dept Comp Sci, College Pk, MD 20742 USA

[3] Univ Maryland, Inst Adv Comp Studies, College Pk, MD 20742 USA

来源：

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS | 1992年 / 2卷 / 02期

基金：

美国国家科学基金会;

关键词：

Minimum enclosures; convex polygons; parallel algorithms; rotating calipers;

D O I：

10.1142/S0218195992000123

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We consider the problems of computing the largest area triangle enclosed within a given n-sided convex polygon and the smallest area triangle which encloses a given convex polygon. We show that these problems are closely related by presenting a single sequential linear time algorithm which essentially solves both problems simultaneously. We also present a cost-optimal parallel algorithm that solves both of these problems in O (log log n) time using n/log log n processors on a CRCW PRAM. In order to achieve these bounds we develop new techniques for the design of parallel algorithms for computational problems involving the rotating calipers method.

引用

页码：191 / 214

页数：24

共 12 条

[1]

Aggarwal A., 1988, 29th Annual Symposium on Foundations of Computer Science (IEEE Cat. No.88CH2652-6), P497, DOI 10.1109/SFCS.1988.21966

[2] PARALLEL COMPUTATIONAL GEOMETRY [J].

AGGARWAL, A ;

CHAZELLE, B ;

GUIBAS, L ;

ODUNLAING, C ;

YAP, C .

ALGORITHMICA, 1988, 3 (03) :293-327

[3] FINDING EXTREMAL POLYGONS [J].

BOYCE, JE ;

DOBKIN, DP ;

DRYSDALE, RL ;

GUIBAS, LJ .

SIAM JOURNAL ON COMPUTING, 1985, 14 (01) :134-147

[4]

Chang J. S., 1984, 25th Annual Symposium on Foundations of Computer Science (Cat. No. 84CH2085-9), P408, DOI 10.1109/SFCS.1984.715942

[5]

DePano N.A.A., 1987, THESIS J HOPKINS U

[6]

Dobkin D. P., 1979, 20th Annual Symposium of Foundations of Computer Science, P9, DOI 10.1109/SFCS.1979.28

[7] RELATIONS BETWEEN CONCURRENT-WRITE MODELS OF PARALLEL COMPUTATION [J].

FICH, FE ;

RAGDE, P ;

WIGDERSON, A .

SIAM JOURNAL ON COMPUTING, 1988, 17 (03) :606-627

[8] FINDING THE SMALLEST TRIANGLES CONTAINING A GIVEN CONVEX POLYGON [J].

KLEE, V ;

LASKOWSKI, MC .

JOURNAL OF ALGORITHMS, 1985, 6 (03) :359-375

[9]

KRUSKAL CP, 1983, IEEE T COMPUT, V32, P942, DOI 10.1109/TC.1983.1676138

[10]

Mount D. M., 1988, Proceedings. Twenty-Sixth Annual Allerton Conference on Communication, Control, and Computing, P87

← 1 2 →