TRIANGULATING A NONCONVEX POLYTOPE

被引：71

作者：

CHAZELLE, B

PALIOS, L

机构：

[1] Department of Computer Science, Princeton University, Princeton, 08544, NJ

来源：

DISCRETE & COMPUTATIONAL GEOMETRY | 1990年 / 5卷 / 05期

关键词：

D O I：

10.1007/BF02187807

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

This paper is concerned with the problem of partitioning a three-dimensional nonconvex polytope into a small number of elementary convex parts. The need for such decompositions arises in tool design, computer-aided manufacturing, finite-element methods, and robotics. Our main result is an algorithm for decomposing a nonconvex polytope of zero genus with n vertices and r reflex edges into O(n +r2) tetrahedra. This bound is asymptotically tight in the worst case. The algorithm requires O(n +r2) space and runs in O((n +r2) log r) time. © 1990 Springer-Verlag New York Inc.

引用

页码：505 / 526

页数：22

共 29 条

[1]

BAJAJ CL, 1989, ROBUST DECOMPOSITION

[2] NONOBTUSE TRIANGULATION OF POLYGONS [J].

BAKER, BS ;

GROSSE, E ;

RAFFERTY, CS .

DISCRETE & COMPUTATIONAL GEOMETRY, 1988, 3 (02) :147-168

[3]

BAKER TJ, 1986, 3 DIMENSIONAL MESH G

[4]

Baumgart BG, 1975, AFIPS P, P589, DOI DOI 10.1145/1499949.1500071

[5]

Canny J., 1987, 28th Annual Symposium on Foundations of Computer Science (Cat. No.87CH2471-1), P39, DOI 10.1109/SFCS.1987.1

[6] THE POWER OF GEOMETRIC DUALITY [J].

CHAZELLE, B ;

GUIBAS, LJ ;

LEE, DT .

BIT, 1985, 25 (01) :76-90

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

CHAZELLE, B .

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

[8]

CHAZELLE B, 1989, LECT NOTES COMPUT SC, V372, P179

[9]

CHAZELLE B., 1987, ADV ROBOTICS, P145

[10]

Collins G. E., 1975, LECT NOTES COMPUT SC, V33, P134, DOI [DOI 10.1007/3-540-07407-4_17, 10.1007/3-540-07407-4_17]

← 1 2 3 →