ABSTRACT
A triangulation [1,2] is a partition of a d-dimensional polytope into simplices. The decomposed simplices should be nonoverlapping except sharing the common vertices (0-faces), edges (1-faces), faces (2-faces), . . . , (d − 1)-faces. When d = 2, a triangulation is the subdivision of a two-dimensional (2D) region into empty triangles, in which two adjacent triangles share an edge. When d = 3, a triangulation, sometimes called tetrahedralization, can be viewed as a decomposition of a three-dimensional (3D) volume into a set of disjoint 3D empty tetrahedra in which two adjacent tetrahedra share a face. Triangulation is not only an interesting theoretical problem in computational geometry, it also has many important applications, such as finite element methods [3] for computer-aided design and physical simulations.
