Two Algorithms for Decomposing a Polyhedron into Convex Parts
- 1 September 1986
- journal article
- Published by Wiley in Computer Graphics Forum
- Vol. 5 (3) , 197-201
- https://doi.org/10.1111/j.1467-8659.1986.tb00298.x
Abstract
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(DNlogN), 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.Keywords
This publication has 4 references indexed in Scilit:
- An Algorithm for Determining the Intersection of Two Simple PolyhedraComputer Graphics Forum, 1984
- A decision procedure for optimal polyhedron partitioningInformation Processing Letters, 1983
- Line/Polygon Classification: A Study of the Complexity of Geometric ComputationIEEE Computer Graphics and Applications, 1981
- Finding the intersection of two convex polyhedraTheoretical Computer Science, 1978