Two Algorithms for Decomposing a Polyhedron into Convex Parts

Abstract

Two algorithms are presented for splitting a polyhedron into convex components: one for the case of a simple polyhedron and one for a more general case, when the polyhedron may have ring-shaped faces and cavities. The time requirement in both cases is O(DNlogN), where D is the number of concave dihedral angles and N is the number of edges. The algorithm for the simple oasis produces at most D+ 1 convex pieces which is the minimal number of the convex components.