Fast Parallel Triangulation Algorithm of Large Data Sets in E2 and E3 for In-Core and Out-Core Memory Processing

Abstract. A triangulation of points in , or a tetrahedronization of points in , is used in many applications. It is not necessary to fulfill the Delaunay criteria in all cases. For large data (more then 5 ∙ 10 points), parallel methods are used for the purpose of decreasing time complexity. A new approach for fast and effective parallel CPU and GPU triangulation, or tetrahedronization, of large data sets in or , is proposed in this paper. Experimental results show that the triangulation/tetrahedralization, is close to the Delaunay triangulation/tetrahedralization. It also demonstrates the applicability of the method presented in applications.