Fast Parallel Triangulation Algorithm of Large Data Sets in E~2 and E~2 for In-Core and Out-Core Memory Processing

摘要

A triangulation of points in E~2, or a tetrahedronization of points in E~3, is used in many applications. It is not necessary to fulfill the Delaunay criteria in all cases. For large data (more then 5 • 10~7 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 E~2 or E~3, 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.