The 3D triangulation algorithm of CGAL is highly efficient. Because the Convex hull is a subset of the 3D triangulation, the idea is to use the 3D triangulation to compute a new 3D convex hull algorithm. To this end, a greedy approach is used for maximizing the size of tetrahedra in the triangulation by choosing the order of insertion. Consequently, points which already appear inside the convex hull are not triangulated.

Softs :