A data-parallel algorithm for three-dimensional Delaunay triangulation and its implementation

A parallel algorithm for constructing the Delaunay triangulation of a set of vertices in three-dimensional space is presented. The algorithm achieves a high degree of parallelism by starting the construction from every vertex and expanding over all open faces thereafter. In the expansion of open faces, the search is made faster by using a bucketing technique. The algorithm is designed under a data-parallel paradigm. It uses segmented list structures and virtual processing for load-balancing. As a result, the algorithm achieves a fast running time and good scalability over a wide range of problem sizes and machine sizes. A topological check is incorporated to eliminate inconsistencies due to degeneracies and numerical errors. The algorithm is implemented on Connection Machines CM-2 and CM-5, and experimental results are presented.