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.

CEMAT - Center for Computational and Stochastic Mathematics