POLYGON NESTING AND ROBUSTNESS

被引：9

作者：

BAJAJ, CL

DEY, T

机构：

[1] Department of Computer Science, Purdue University, West Lafayette

来源：

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

基金：

美国国家科学基金会;

关键词：

analysis of algorithms; Computational geometry; computer graphics;

D O I：

10.1016/0020-0190(90)90169-X

中图分类号：

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

学科分类号：

0812 ;

摘要：

We consider the polygon nesting problem for a set of m simple, nonintersecting, planar polygons with n vertices and N notches. We give an O(n + (m + N)log(m + N)) timealgorithm which uses exact arithmetic and give an O(n(log n + m + N)) time, robust algorithm which uses floating point arithmetic. © 1990.

引用

页码：23 / 32

页数：10

共 15 条

[1]

BAJAJ C, 1989, MATH SURFACES, V3

[2]

BAJAJ CL, 1989, LECT NOTES COMPUT SC, V405, P267

[3] CONVEX PARTITIONS OF POLYHEDRA - A LOWER BOUND AND WORST-CASE OPTIMAL ALGORITHM [J].

CHAZELLE, B .

SIAM JOURNAL ON COMPUTING, 1984, 13 (03) :488-507

[4]

DOBKIN D, 1988, 4TH P ACM S COMP GEO, P93

[5] TOPOLOGICALLY SWEEPING AN ARRANGEMENT [J].

EDELSBRUNNER, H ;

GUIBAS, LJ .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1989, 38 (01) :165-194

[6]

EDELSBRUNNER H, 1988, 4TH P ACM S COMP GEO, P118

[7]

FORTUNE S, 1989, UNPUB STABLE MAINTEN

[8]

Greene D. H., 1986, 27th Annual Symposium on Foundations of Computer Science (Cat. No.86CH2354-9), P143, DOI 10.1109/SFCS.1986.19

[9]

HOFFMANN C, 1987, 87875 CORN U DEP COM

[10]

KARASICK M, 1988, THESIS MCGILL U MONT

← 1 2 →