The problem of partitioning a polyhedron into a minimum number of convex pieces is known to be NP-hard. The author establishes here a quadratic lower bound on the complexity of this problem, and he describes an algorithm that produces a number of convex parts within a constant factor of optimal in the worst case. The algorithm is linear in the size of the polyhedron and cubic in the number of reflex angles. Since in most applications areas, the former quantity greatly exceeds the latter, the algorithm is viable in practice.
All Science Journal Classification (ASJC) codes
- General Computer Science
- General Mathematics