Filters

20152

More filters

20192
Reset filters

Settings

Author: Goerigk, Nadja × Type: Report ×

Search Results

Now showing 1 - 2 of 2
  • Thumbnail Image
    Item
    On tetrahedralisations of reduced Chazelle polyhedra with interior Steiner points
    (Berlin : Weierstraß-Institut für Angewandte Analysis und Stochastik, 2015) Si, Hang; Goerigk, Nadja
    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.
  • Thumbnail Image
    Item
    On indecomposable polyhedra and the number of interior Steiner points
    (Berlin : Weierstraß-Institut für Angewandte Analysis und Stochastik, 2015) Goerigk, Nadja; Si, Hang
    The existence of 3d 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 wellknown examples, the so-called Schönhardt polyhedron [Schönhardt, 1928] and the Bagemihl's generalization of it [Bagemihl, 1948], which will be called Bagemihl polyhedra. We provide a construction of an interior point, so-called 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 ≥ 6 vertices, we show that it can be tetrahedralized by adding at most ... interior Steiner points. We also show that this number is optimal in the worst case.