Parallel Delaunay triangulation—Application to two dimensions

A generic parallel Delaunay triangulation scheme by means of zonal partition of points is presented. For efficient Delaunay triangulation, points are first partitioned into cells, each of which is allocated roughly equal number of points. The cells can be naturally grouped into zones, in which Delaunay triangulation is constructed by simultaneous point insertion cell by cell within each zone. Delaunay triangles/tetrahedra at the boundary between zones can be created in parallel by adding layers of cells at the boundary of each zone to ensure circumcircles(circumspheres) of boundary triangles(tetrahedra) contain no points in their interior. Redundant triangles(tetrahedra) at the boundary between zones can be easily eliminated by individual processors in a completely independent manner by means of the elegant minimum vertex allocation scheme, such that a simplex with k vertices belonging to zones (z1, z2,… zk) is allocated to zone z=min (z1, z2,… zk).A two-dimensional version of the algorithm has been coded in Intel Fortran VS2010. The parallel zonal insertion on a PC can boost the speed of the single-processor insertion by 4.5 times for the insertion of 200 million randomly generated points in 65.7 s. The scalability of the parallel zonal insertion algorithm has also been tested on a proper multi-core machine with 12 processors running on OpenMP parallel directives with shared memory. Provided the number of zones is an integral multiple of the number of processors used, almost 100% scalability at 90% efficiency was observed for parallel insertion using 2, 4, 6, 8, 10 and 12 processors, and a 10.6 time speed up was recorded in a parallel insertion of 20 million points in 10×12=120 zones by 12 processors.

► Linear complexity in Delaunay triangulation of random points.
► Simultaneous zonal insertion in an absolute independent manner.
► Novel treatment at zonal boundary to create Delaunay simplices between zones.
► New minimum vertex allocation scheme for partition of simplices.
► Almost 100% scalability running on OpenMP shared memory systems.