CONVEX DECOMPOSITION OF POLYHEDRA AND ROBUSTNESS

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.