On tetrahedralisations of reduced Chazelle polyhedra with interior Steiner points
- Si, Hang
- Goerigk, Nadja
2010 Mathematics Subject Classification
- 65D18 68U05 65M50, 65N50
- indecomposable polyhedron, Chazelle polyhedron, Schönhardt polyhedron, Steiner points, tetrahedralisation, edge flip
The polyhedron constructed by Chazelle, known as Chazelle polyhedron , is an important example in many partitioning problems. In this paper, we study the problem of tetrahedralising a Chazelle polyhedron without modifying its exterior boundary. It is motivated by a crucial step in 3d finite element mesh generation in which a set of arbitrary boundary constraints (edges or faces) need to be entirely preserved. We first reduce the volume of a Chazelle polyhedron by removing the regions that are tetrahedralisable. This leads to a 3d polyhedron which may not be tetrahedralisable unless extra points, so-called Steiner points, are added. We call it a reduced Chazelle polyhedron. We define a set of interior Steiner points that ensures the existence of a tetrahedralisation of the reduced Chazelle polyhedron. Our proof uses a natural correspondence that any sequence of edge flips converting one triangulation of a convex polygon into another gives a tetrahedralization of a 3d polyhedron which have the two triangulations as its boundary. Finally, we exhibit a larger family of reduced Chazelle polyhedra which includes the same combinatorial structure of the Schönhardt polyhedron. Our placement of interior Steiner points also applies to tetrahedralise polyhedra in this family.
- 25th International Meshing Roundtable, S. Canann, S. Owen, H. Si, eds., vol. 163 of Procedia Engineering, Elsevier, Amsterdam, 2016, pp. 33--45