Parallel Triangulation of a Set of Point for Coarse Grained Multicomputers

In this study we address the problem of ecient parallel triangulation methods for a nite set of points in the plane. The main goals of the research were to identify scalable algorithms which achieve a signicant speedup over the sequential solutions and to implement and evaluate their performance on a parallel machine. Two approaches for parallel triangulation, one of which relies on global sorting, are fully described and implemented on a hypercube. Extensive performanc