Grant: Discovery Grants Program - Individual

Triangulation is to partition an object (a set of points or a simple polygon) into simplices (triangles) and is one of the fundamental problems in Computational Geometry. In addition to its theoretical significance, it finds applications in many areas such as Computer Graphics, Scientific Visualization, and Geological Information Systems. While the problem in 2D is well studied, its 3D counterpart (called `Tetrahedralization') is relatively unexplored. This is because the geometric structure of tetrahedralization is much more complicated. For example, triangulation in 2D is always possible and the number of triangles in different triangulations of a point set is the same. On contrast, not all the 3D non-convex polyhedra can be tetrahedralized without adding Steiner points, and for different tetrahedralizations may have different number of tetrahedra. In the related graph problems in 2D and 3D, the difference also exists. In this proposal, I shall propose the following three main problems: (1) To study tetrahedralizations with different constraints. For example, tetrahedralization with maximum number of tetrahedra and tetrahedralization with max-min inner angle of tetrahedra. (2) To study related graph problems. For example, the Hamiltonian path in any tetrahedralization of a given point set, the connectivity of any two tetrahedralizations by diagonal flips, and the drawability of graphs as a constrained tetrahedralization. (3) To study the sum of the square-root of integer problem, which is important for proving a hard geometric problem to be in NP. Investigating these problems will help us to further understand tetrhedralizations and probably to design algorithms for many applications.