Using partial parallelization to triangulate 2D domains

Delaunay triangulation of an arbitrary domain is one of the fundamental problems of computational geometry. Classical approaches to Delaunay triangulation produce triangles that have a wide range of angle values. The paper proposes an algorithm for triangulation of complex geometry domains taking into account predetermined parameters: the minimum angle and the maximum side length of the obtained triangles. The algorithm consists of three main stages. The first stage takes a set of points that set the figure boundary as input, and forms an initial partition into subdomains from them generating points for further triangulation. Such generation for subdomains is completely independent; therefore, it is most effectively parallelized by the number of logical cores. The figure is then triangulated by the divide-and-conquer algorithm. Here, the highest performance is achieved with the number of threads equal to the number of physical processor cores. At the last stage, the parameters of triangles are refined by a method based on Ruppert's algorithm. Due to the specifics of the algorithm, the serial code is optimal at this stage. All parallelization is implemented using OpenMP technology in C++. The paper shows numerical results representing the increase in computing performance for a different number of threads depending on the problem dimension.