WIAS Preprint No. 2142, (2015)

On indecomposable polyhedra and the number of interior Steiner points



Authors

  • Goerigk, Nadja
  • Si, Hang

2010 Mathematics Subject Classification

  • 65D18 68U05 65M50 65N50

Keywords

  • Indecomposable polyhedra, Steiner points, tetrahedralization, Schönhardt polyhedron, Bagemihl polyhedron, Chazelle polyhedron

Abstract

The existence of 3d it 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. While the geometry and combinatorial structure of such polyhedra are much less studied. In this article, we first investigate the geometry of some well-known examples, the so-called it Schönhardt polyhedron citeSchonhardt1928 and the Bagemihl's generalization of it citeBagemihl48-decomp-polyhedra, which will be called it Bagemihl polyhedra. We provide a construction of an interior point, so-called it Steiner point, which can be used to tetrahedralize the Schönhardt and the Bagemihl 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 Schönhardt and Bagemihl polyhedra, but they may need more than one interior Steiner point to be tetrahedralized. Given such a polyhedron with $n ge 6$ vertices, we show that it can be tetrahedralized by adding at most $leftlceil fracn - 52rightrceil$ interior Steiner points. %, is sufficient to decompose it. We also show that this number is optimal in the worst case.

Appeared in

  • Procedia Engineering, Volume 124, 2015, Pages 343--355

Download Documents