Construction of three-dimensional Delaunay triangulations using local transformations (Q807005)

For a set of points in \(R^ 3\) the problem of Delaunay triangulation is to find a set of nonoverlapping tetrahedra that fill the convex hull of the set so that no point is in the circumscribed sphere of any tetrahedron of which it is not a vertex. The author gives the pseudocode description of two programs that solve the problem by local decisions involving five points at a time and proves that the worst case time complexity is \(O(n^ 2)\) and the expected complexity for random points is O(n(log n)\({}^ 2)\).