Two Algorithms for Decomposing a Polyhedron into Convex Parts
No Thumbnail Available
Date
1986
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Blackwell Publishing Ltd and the Eurographics Association
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.
Description
@article{10.1111:j.1467-8659.1986.tb00298.x,
journal = {Computer Graphics Forum},
title = {{Two Algorithms for Decomposing a Polyhedron into Convex Parts}},
author = {Szilvasi-Nagy, M.},
year = {1986},
publisher = {Blackwell Publishing Ltd and the Eurographics Association},
ISSN = {1467-8659},
DOI = {10.1111/j.1467-8659.1986.tb00298.x}
}