Construction of K -Dimensional Delaunay Triangulations Using Local Transformations
Barry Joe · SIAM Journal on Scientific Computing · 1993
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 nk-dimensional points for any $k \geq 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 \geq 3$).