Abstract: This paper proposed a planar Delaunay triangulation algorithm based on parallel 2D convex hull algorithm．The proposed algorithm is based on the parallel 2D convex hull algorithm proposed in literature [20] by Jian Yan,etc．It constructs an initial triangulation by recording the grown edges and the removed points during the convex hull buil-ding,then constructs partial Delaunay triangulation through point by point method inside each triangle of the initial triangulation,finally locally optimizes the boundary edges of the local Delaunay triangulations to get the Delaunay triangulation of the whole origin set．The correctness of the algorithm was discussed.And the experiment results show that the algorithm is efficient and stable.

Key words: Convex hull,Delaunay triangulation,Parallel algorithm