Convex decompositions of polyhedra

Research output: Chapter in Book/Report/Conference proceedingConference contribution

50 Scopus citations


An important direction of research in computational geometry has been to find methods for decomposing complex structures into simpler components. In this paper, we examine the problem of decomposing a threedimensional polyhedron P into a minimal number of convex pieces. Letting n be the number of vertices in P and N the number of edges which exhibit a reflex angle (i.e. the notches of P), our main result is an O(nN3) time algorithm for computing a convex decomposition of P. The algorithm produces O(N2) convex parts, which is optimal in the worst case. In most situations where the problem arises (e.g, graphics, tool design, pattern recognition), the number of notches N seems greatly dominated by the number of vertices n; the algorithm is therefore viable in practice.

Original languageEnglish (US)
Title of host publicationConference Proceedings of the 13th Annual ACM Symposium on Theory of Computing, STOC 1981
PublisherAssociation for Computing Machinery
Number of pages10
ISBN (Print)0897910419
StatePublished - May 11 1981
Externally publishedYes
Event13th Annual ACM Symposium on Theory of Computing, STOC 1981 - Milwaukee, United States
Duration: Jun 11 1981Jun 13 1981

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017


Other13th Annual ACM Symposium on Theory of Computing, STOC 1981
Country/TerritoryUnited States

All Science Journal Classification (ASJC) codes

  • Software


Dive into the research topics of 'Convex decompositions of polyhedra'. Together they form a unique fingerprint.

Cite this