Premium
Two Algorithms for Decomposing a Polyhedron into Convex Parts
Author(s) -
SzilvásiNagy M.
Publication year - 1986
Publication title -
computer graphics forum
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.578
H-Index - 120
eISSN - 1467-8659
pISSN - 0167-7055
DOI - 10.1111/j.1467-8659.1986.tb00298.x
Subject(s) - polyhedron , regular polygon , convex polytope , simple (philosophy) , combinatorics , dihedral angle , mathematics , algorithm , computer science , convex set , geometry , convex optimization , philosophy , hydrogen bond , epistemology , molecule , chemistry , organic chemistry
Two algorithms are presented for splitting a polyhedron into convex components: one for the case of a simple polyhedron and one for a more general case, when the polyhedron may have ring‐shaped faces and cavities. The time requirement in both cases is O ( DN log N ), where D is the number of concave dihedral angles and N is the number of edges. The algorithm for the simple oasis produces at most D + 1 convex pieces which is the minimal number of the convex components.