Parallel Triangulation of a Set of Points for Coarse Grained Multicomputers

In this study we address the problem of efficient parallel triangulation methods for a finite set of points in the plane. The main goals of the research were to identify scalable algorithms which achieve a significant 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 performance evaluation in expected average and worst cases is reported for both methodsTechnical report DCS-TR-31