The corresponding optimization problem is shown to be NP-complete and an experimental search for good heuristics is undertaken. 1 Introduction Convex shapes are easiest to represent, manipulate, and render. Even though they form the building blocks of bottom-up solid modelers, it is more often the case that the convex structure of a geometric shape is lost in its representation.
Convex decomposition has many applications and is currently a bottleneck.
On visible surface generation by a priori tree structures - Fuchs, Kedem et al. Provably good mesh generation - Bern, Eppstein et al. Convex surface Decomposition - Chazelle, Dobkin et al.