AN O(N-LOG LOG-N)-TIME ALGORITHM FOR TRIANGULATING A SIMPLE POLYGON

被引：88

作者：

TARJAN, RE ^{[1
]}

VANWYK, CJ ^{[1
]}

机构：

[1] PRINCETON UNIV,DEPT COMP SCI,PRINCETON,NJ 08544

来源：

SIAM JOURNAL ON COMPUTING | 1988年 / 17卷 / 01期

关键词：

Mathematical Techniques--Geometry;

D O I：

10.1137/0217010

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Given a simple n-vertex polygon, the triangulation problem is to partition the interior of the polygon into n-2 triangles by adding n-3 nonintersecting diagonals. We propose an O(n log log n)-time algorithm for this problem, improving on the previous best bound of O(n log n) and showing that triangulation is not as hard as sorting Improved algorithms for several other computational geometry problems, including testing whether a polygon is simple, follow from our result.

引用

页码：143 / 178

页数：36

共 31 条

[1]

BHATTACHARYA B, 1986, SOCS861 MCGILL U SCH

[2] DESIGN AND ANALYSIS OF A DATA STRUCTURE FOR REPRESENTING SORTED LISTS [J].

BROWN, MR ;

TARJAN, RE .

SIAM JOURNAL ON COMPUTING, 1980, 9 (03) :594-614

[3]

Chazelle B., 1982, 23rd Annual Symposium on Foundations of Computer Science, P339, DOI 10.1109/SFCS.1982.58

[4] TRIANGULATION AND SHAPE-COMPLEXITY [J].

CHAZELLE, B ;

INCERPI, J .

ACM TRANSACTIONS ON GRAPHICS, 1984, 3 (02) :135-152

[5]

CHAZELLE B, 1984, 16TH ACM S THEOR COM, P125

[6]

CHIN WP, 1986, 2ND P ACM S COMP GEO, P24

[7]

DOBKIN DP, IN PRESS ALGORITHMIC

[8] OPTIMAL POINT LOCATION IN A MONOTONE SUBDIVISION [J].

EDELSBRUNNER, H ;

GUIBAS, LJ ;

STOLFI, J .

SIAM JOURNAL ON COMPUTING, 1986, 15 (02) :317-340

[9] TRIANGULATING SIMPLE POLYGONS AND EQUIVALENT PROBLEMS [J].

FOURNIER, A ;

MONTUNO, DY .

ACM TRANSACTIONS ON GRAPHICS, 1984, 3 (02) :153-174

[10] TRIANGULATING A SIMPLE POLYGON [J].

GAREY, MR ;

JOHNSON, DS ;

PREPARATA, FP ;

TARJAN, RE .

INFORMATION PROCESSING LETTERS, 1978, 7 (04) :175-179

← 1 2 3 4 →