carrier image

On Tetrahedralisations of Reduced Chazelle Polyhedra with Interior Steiner Points

Si, Hang, Nadja Goerigk

Proceedings, 25th International Meshing Roundtable, Elsevier, Science Direct, September 26-30 2016

INTERNATIONAL
MESHING
ROUNTABLE

25th International Meshing Roundtable
Washington DC, U.S.A.
September 26-30, 2016

Hang Si, WIAS Berlin, DE, si@wias-berlin.de
Nadja Goerigk, , DE, nadja.goerigk@yahoo.de

Abstract
The non-convex polyhedron constructed by Chazelle, known as the {\it Chazelle polyhedron}~\cite{Chazelle1984}, establishes a quadratic lower bound on the minimum number of convex pieces for the 3d polyhedron partitioning problem. In this paper, we study the problem of tetrahedralising the Chazelle polyhedron without modifying its exterior boundary. It is motivated by a crucial step in tetrahedral mesh generation in which a set of arbitrary constraints (edges or faces) need to be entirely preserved. The goal of this study is to gain more knowledge about the family of 3d indecomposable polyhedra, and to tetrahedralise them efficiently. The requirement of only using interior Steiner points for the Chazelle polyhedron is extremely challenging. We first cut off the volume of the Chazelle polyhedron by removing the regions that are tetrahedralisable. This leads to a 3d non-convex polyhedron whose vertices are all in the two slightly shifted saddle surfaces which are used to construct the Chazelle polyhedron. We call it the {\it reduced Chazelle polyhedron}. It is an indecomposable polyhedron. We then give a set of $(N+1)^2$ interior Steiner points that ensures the existence of a tetrahedralisation of the reduced Chazelle polyhedron with $4(N+1)$ vertices. 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. Our placement of interior Steiner points also applies to tetrahedralise polyhedra in this family.

Download Full Paper (PDF)


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