Convex decompositions of polyhedra

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

36 Scopus citations

Abstract

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
Pages70-79
Number of pages10
ISBN (Print)0897910419
DOIs
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

Other

Other13th Annual ACM Symposium on Theory of Computing, STOC 1981
CountryUnited States
CityMilwaukee
Period6/11/816/13/81

All Science Journal Classification (ASJC) codes

  • Software

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

  • Cite this

    Chazelle, B. M. (1981). Convex decompositions of polyhedra. In Conference Proceedings of the 13th Annual ACM Symposium on Theory of Computing, STOC 1981 (pp. 70-79). (Proceedings of the Annual ACM Symposium on Theory of Computing). Association for Computing Machinery. https://doi.org/10.1145/800076.802459