Point Triangulation using Grahamâ€™s Scan
Vasyl Tereshchenko, Yaroslav Tereshchenko
Journal of Data Processing, Vol. 4, No. 3, 2014.
DOI: 
Link: 
Abstract:
In this paper, we propose a triangulation method for a set of points in the plane. The method is based on the idea of constructing convex layers  by Grahamâ€™s scan. It allows to develop an algorithm with the optimal complexity of O(NlogN)
and an easy implementation. First, convex hulls are constructed for the set S of N points, forming k layers. Then, each layer is
triangulated in one scan of the adjacent convex hulls. Algorithm is easily parallelized: each layer can be triangulated independently. The main feature of the proposed algorithm is that it has a very simple implementation and the elements
(triangles) of the resulting triangulation are presented in the form of simple and at the same time fast data structures: concatenable triangle queue or triangle tree. This makes the algorithm convenient for solving a wide range of applied
problems of computational geometry and computer graphics, including simulation in science and engineering, rendering and morphing.