Triangulations and Simplex Tilings of Polyhedra

Abstract

This dissertation summarizes my research in the area of Discrete Geometry. The particular problems of Discrete Geometry discussed in this dissertation are concerned with partitioning three dimensional polyhedra into tetrahedra. The most widely used partition of a polyhedra is triangulation, where a polyhedron is broken into a set of convex polyhedra all with four vertices, called tetrahedra, joined together in a face-to-face manner. If one does not require that the tetrahedra to meet along common faces, then we say that the partition is a tiling.

Many of the algorithmic implementations in the field of Computational Geometry are dependent on the results of triangulation. For example computing the volume of a polyhedron is done by adding volumes of tetrahedra of a triangulation. In Chapter 2 we will provide a brief history of triangulation and present a number of known non-triangulable polyhedra. In this dissertation we will particularly address non-triangulable polyhedra.

Our research was motivated by a recent paper of J. Rambau, who showed that a nonconvex twisted prisms cannot be triangulated. As in algebra when proving a number is not divisible by 2012 one may show it is not divisible by 2, we will revisit Rambau's results and show a new shorter proof that the twisted prism is non-triangulable by proving it is non-tilable. In doing so, we identify a new family of nonconvex non-tilable polyhedra, which we call an altered right prism. Furthermore we will perturb the vertices of a regular dodecahedron in a twisted manner resulting in a non-tilable polyhedra. Also for completeness, we describe two concrete non-triangulable polyhedra which can be tiled with tetrahedra.

From observations made about the provided non-triangulable polyhedra, we started to systematically study extensions of surface triangulations of convex polyhedra. Among others we proved that if each vertex of a convex polyhedron is adjacent to no more than three non-triangular faces, then for every surface triangulation one can perturb the vertices of the polyhedron so that the resulting polyhedron is combinatorially equivalent to the given surface triangulation.