A parallel algorithm based on convexity for the computing of Delaunay tessellation

The paper describes a parallel algorithm for computing an n‐dimensional Delaunay tessellation using a divide‐conquer strategy. Its implementation (using MPI library for C) in the case n = 2, relied on restricted areas to discard non‐Delaunay edges, is executed easily on PC clusters. We shows that the convexity is a crucial factor of efficiency of the parallel implementation over the corresponding sequential one.