Structures of Triangulations of Points

Keiko IMAI  

IEICE TRANSACTIONS on Information and Systems   Vol.E83-D    No.3    pp.428-437
Publication Date: 2000/03/25
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: INVITED SURVEY PAPER
Category: Algorithms for Geometric Problems
triangulation,  tetrahedralization,  delaunay triangulation,  regular triangulation,  convex polytope,  computational geometry,  

Full Text: PDF>>
Buy this Article

Triangulations have been one of main research topics in computational geometry and have many applications in computer graphics, finite element methods, mesh generation, etc. This paper surveys properties of triangulations in the two- or higher-dimensional spaces. For triangulations of the planar point set, we have a good triangulation, called the Delaunay triangulation, which satisfies several optimality criteria. Based on Delaunay triangulations, many properties of planar triangulations can be shown, and a graph structure can be constructed for all planar triangulations. On the other hand, triangulations in higher dimensions are much more complicated than in planar cases. However, there does exist a subclass of triangulations, called regular triangulations, with nice structure, which is also touched upon.