WIAS Preprint No. 2190, (2015)

On tetrahedralisations of reduced Chazelle polyhedra with interior Steiner points



Authors

  • Si, Hang
  • Goerigk, Nadja

2010 Mathematics Subject Classification

  • 65D18 68U05 65M50, 65N50

Keywords

  • indecomposable polyhedron, Chazelle polyhedron, Schönhardt polyhedron, Steiner points, tetrahedralisation, edge flip

DOI

10.20347/WIAS.PREPRINT.2190

Abstract

The polyhedron constructed by Chazelle, known as Chazelle polyhedron [4], 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.

Appeared in

  • 25th International Meshing Roundtable, S. Canann, S. Owen, H. Si, eds., vol. 163 of Procedia Engineering, Elsevier, Amsterdam, 2016, pp. 33--45

Download Documents