@article{1686,
  author = {Vasyl Tereshchenko, Yaroslav Tereshchenko},
  title = {Point Triangulation using Graham’s Scan},
  journal = {Journal of Data Processing},
  year = {2014},
  volume = {4},
  number = {3},
  doi = {},
  url = {},
  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.},
}