Delaunay Triangulation Cutting Algorithm for A Set of Irregularly Located Spatial Points

Maximum empty-circle convex polygon and maximum empty-sphere convex polyhedron are introduced to compute triangulation on a set of irregularly located spatial points. The domain bounded by the convex hull of a set of spatial points is divided to maximum empty-sphere convex polyhedrons firstly, then the triangulation is followed inside these polyhedrons. This method successfully solves the degeneracy problem of more than three points on a plane sharing a common circle or more than four spatial points sharing a common sphere. A possible error occurring in a class of triangulation algorithms is presented in this paper.