COMPUTING THE LONGEST DIAGONAL OF A SIMPLE POLYGON

被引：6

作者：

AGGARWAL, A ^{[1
]}

SURI, S ^{[1
]}

机构：

[1] BELL COMMUN RES INC,MORRISTOWN,NJ

来源：

INFORMATION PROCESSING LETTERS | 1990年 / 35卷 / 01期

关键词：

Analysis of algorithms; computational geometry; longest diagonal; polygons;

D O I：

10.1016/0020-0190(90)90167-V

中图分类号：

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

学科分类号：

0812 ;

摘要：

An O(n log3n) algorithm is presented for computing the longest diagonal of a simple n-gon. The longest diagonal problem requires the determination of two vertices of the polygon that are visible to each other and that are farthest from each other among all such pairs. This problem is a variation of the "biggest stick" problem for which the most efficient algorithm that is known, is O(n1.98) time. © 1990.

引用

页码：13 / 18

页数：6

共 8 条

[1] GEOMETRIC APPLICATIONS OF A MATRIX-SEARCHING ALGORITHM [J].

AGGARWAL, A ;

KLAWE, MM ;

MORAN, S ;

SHOR, P ;

WILBER, R .

ALGORITHMICA, 1987, 2 (02) :195-208

[2]

AGGARWAL A, IN PRESS 1989 P WORK

[3]

CHAZELLE B, 1985, 1ST P ACM S COMP GEO, P135

[4]

CHAZELLE BM, 1988, ALGORITHM GENERALIZE

[5]

CHAZELLE BM, 1983, 23RD P IEEE ANN S F, P339

[6] A LINEAR ALGORITHM FOR COMPUTING THE VISIBILITY POLYGON FROM A POINT [J].

ELGINDY, H ;

AVIS, D .

JOURNAL OF ALGORITHMS, 1981, 2 (02) :186-197

[7]

MCKENNA M, 1986, 1ST COMPUTATIONAL GE

[8]

[No title captured]

← 1 →