Convex Decomposition of Polyhedra and Robustness

Abstract

This paper presents a simple algorithm to compute a convex decomposition of a nonconvex polyhedron of arbitrary genus (handles) and shells (internal voids). For such a polyhedron S with n edges and rnotches (features causing nonconvexity in polyhedra), the algorithm produces a worst-case optimal $O(r^2 )$ number of convex polyhedra $S_i $, with $U_{i = 1}^k S_i = S$, in $O(nr^2 + r^{7/2} )$ time and $O(nr + r^{5/2} )$ space. Recently, Chazelle and Palios have given a fast $O((n + r^2 )\log r$) time and $O(n + r^2 )$ space algorithm to tetrahedralize a nonconvex polyhedron. Their algorithm, 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 is quite efficient. The algorithm is extended to work for a certain class of nonmanifold polyhedra. Also presented is an algorithm for the same problem that uses clever heuristics to overcome the numerical inaccuracies under finite precision arithmetic.