CONVEX DECOMPOSITION OF POLYHEDRA AND ROBUSTNESS

Authors
Citation
Cl. Bajaj et Tk. Dey, CONVEX DECOMPOSITION OF POLYHEDRA AND ROBUSTNESS, SIAM journal on computing, 21(2), 1992, pp. 339-364
Citations number
29
Language
INGLESE
art.tipo
Article
Journal title
ISSN journal
0097-5397
Volume
21
Issue
2
Year of publication
1992
Pages
339 - 364
Database
ISI
SICI code
0097-5397(1992)21:2<339:CDOPAR>2.0.ZU;2-2
Abstract
This paper presents a simple algorithm to compute a convex decompositi on of a nonconvex polyhedron of arbitrary genus (handles) and shells ( internal voids). For such a polyhedron S with n edges and r notches (f eatures causing nonconvexity in polyhedra), the algorithm produces a w orst-case optimal O(r2) number of convex polyhedra S(i), with or(i=1)( k)S(i) = S, in O(nr2 + r7/2) time and O(nr + r5/2) space. Recently, Ch azelle and Palios have given a fast O((n + r2) log r) time and O(n + r 2) space algorithm to tetrahedralize a nonconvex polyhedron. Their alg orithm, however, works for a simple polyhedron of genus zero and with no shells (internal voids). The algorithm, presented here, is based on the simple cut and split paradigm of Chazelle. With the help of zone theorems on arrangements, it is shown that this cut and split method i s quite efficient. The algorithm is extended to work for a certain cla ss of nonmanifold polyhedra. Also presented is an algorithm for the sa me problem that uses clever heuristics to overcome the numerical inacc uracies under finite precision arithmetic.