A Parallel Algorithm Based on Convexity for the Computing of Delaunay Tessellation
An, P. T. ; Trang, L. H.
Numerical Algorithms, 59(3) (2012), 347-357
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.