CONSTRUCTION OF K-DIMENSIONAL DELAUNAY TRIANGULATIONS USING LOCAL TRANSFORMATIONS

In [SIAM J. Sci. Statist. Comput., 10 (1989), pp. 718-741] and [Comput. Aided Geom. Des., 8 (1991), pp. 123-142] the author presented algorithms that use local transformations to construct a Delaunay triangulation of a set of n three-dimensional points. This paper proves that local transformations can be used to construct a Delaunay triangulation of a set of n k-dimensional points for any k greater-than-or-equal-to 2, and presents algorithms using this approach. The empirical time complexities of these algorithms are discussed for sets of random points from the uniform distribution as well as worst-case time complexities. These time complexities are about the same or better than those of other algorithms for constructing k-dimensional Delaunay triangulations (when k greater-than-or-equal-to 3).