A data-parallel algorithm for three-dimensional Delaunay triangulation and its implementation
Yuan‐Hsiang Teng, Frank Sullivan, Isabel M. Beichl, Enrico Puppo · 1993
In this paper, we present a parallel algorithm for constructing the Delaunay triangulation of a set of vertices in three-dimensional space.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.We also incorporate a topological check 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.finite element methods.