The parallelization of Delaunay triangulation algorithms has been investigated, with different solutions designed and evaluated.
The first one, which is a parallel implementation of the
Divide & Conquer paradigm, was faster but showed limited scalability.
The second one operates a regular geometric partition of the dataset and subdivides the
load among m independent asynchronous processors, using on each node a modified
version of an incremental construction algorithm (InCoDe); this solution is
algorithmically quite simple and allows sufficiently good scalability.
In order to increase the scalability of the parallel incremental construction method, a
hybrid strategy has been proposed in a further paper. This
solution composes a space decomposition approach with a master-slave one. The hybrid
parallel algorithm allows the threshold to be raised on the number of processors over
which the efficiency of the other two solutions become unacceptable.
Abstract
This paper deals with the parallelization of Delaunay triangulation, a
widely used space partitioning technique. Two parallel implementations of a
three-dimensional incremental construction algorithm are presented. The first is
based on the decomposition of the spatial domain, while the second relies on the
master-slaves approach.
Both parallelization strategies are evaluated, stressing practical issues rather than
theoretical complexity. We report on the exploitation of two different parallel
environments: a tightly-coupled distributed memory MIMD architecture and a network of
workstations cooperating under the Linda environment. Then, a third hybrid solution is
proposed, specifically addressed to the exploitation of higher parallelism. It combines
the other two solutions by grouping the processing nodes of the multicomputer into
clusters and by exploiting parallelism at two different levels.
Parallel 3D Delaunay triangulation
Abstract
The paper deals with the parallelization of Delaunay triangulation
algorithms, giving more emphasis to pratical issues and implementation than to theoretical
complexity. Two parallel implementations are presented. The first one is built on DeWall,
an Ed triangulator based on an original interpretation of the divide &
conquer paradigm. The second is based on an incremental construction algorithm. The
parallelization strategies are presented and evaluated. The target parallel machine is a
distributed computing environment, composed of coarse grain processing nodes. Results of
first implementations are reported and compared with the performance of the serial
versions running on a Unix workstation.