Three-Dimensional Triangulations from Local Transformations

A new algorithm is presented that uses a local transformation procedure to construct a triangulation of a set of n three-dimensional points that is pseudo-locally optimal with respect to the sphere criterion. It is conjectured that this algorithm always constructs a Delaunay triangulation, and this conjecture is supported with experimental results. The empirical time complexity of this algorithm is O(n^4 / 3 ) for sets of random points, which compares well with existing algorithms for constructing a three-dimensional Delaunay triangulation. Also presented is a modification of this algorithm for the case that local optimality is based on the max-min solid angle criterion.