Implementation of a randomized algorithm for Delaunay and regular triangulations in three dimensions Original Research Article

For a set of n points in R3, we can define the Delaunay triangulation of the point set. For each assignment of weights to the points there is a regular triangulation of the point set. We describe the implementation of algorithms to compute the Delaunay triangulation of an unweighted point set and the regular triangulation of a weighted point set. The algorithms run in expected time O(n log n) for uniformly distributed points and other dense point sets. Worst case point sets, which do not occur very often in practice, require O(n2) expected time. The software described in this paper is available via anonymous ftp at ftp.ncsa.uiuc.edu.