carrier image

On Indecomposable Polyhedra and The Number of Steiner Points

Goerigk, Nadja ,Hang Si

24th International Meshing Roundtable, Elsevier Ltd., October 12-14 2015


24th International Meshing Roundtable
Austin, TX
October 12-14,2014

Weierstrass Institute, Mohrenstr. 39, 10117 Berlin, Germany

The existence of indecomposable polyhedra, that is, the interior of every such polyhedron cannot be decomposed into a set of tetrahedra whose vertices are all of the given polyhedron, is well-known. However, the geometry and combinatorial structure of such polyhedra are much less studied. In this article, we investigate the structure of some well-known examples, the so-called Schonhardt polyhedron [10] and the Bagemihl's generalization of it [1], which will be called Bagemihl's polyhedra. We provide a construction of an additional point, so-called Steiner point, which can be used to decompose the Schonhardt and the Bagemihl's polyhedra. We then provide a construction of a larger class of three-dimensional indecomposable polyhedra which often appear in grid generation problems. We show that such polyhedra have the same combinatorial structure as the Schonhardt's and Bagemihl's polyhedra, but they may need more than one Steiner point to be decomposed. Given such a polyhedron with n  6 vertices, we show that it can be decomposed by adding at most (n-5)/2 interior Steiner points. We also show that this number is optimal in the worst case.

Download Full Paper (PDF Format)

Contact author(s) or publisher for availability and copyright information on above referenced article