TY - GEN

T1 - Convex decompositions of polyhedra

AU - Chazelle, Bernard M.

PY - 1981/5/11

Y1 - 1981/5/11

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=79551589374&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=79551589374&partnerID=8YFLogxK

U2 - 10.1145/800076.802459

DO - 10.1145/800076.802459

M3 - Conference contribution

AN - SCOPUS:79551589374

SN - 0897910419

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 70

EP - 79

BT - Conference Proceedings of the 13th Annual ACM Symposium on Theory of Computing, STOC 1981

PB - Association for Computing Machinery

T2 - 13th Annual ACM Symposium on Theory of Computing, STOC 1981

Y2 - 11 June 1981 through 13 June 1981

ER -