Implementation of a Randomized Algorithm for Delaunay and Regular Triangulations in Three Dimensions
Facello, Michael, A.
Computer Aided Geometric Design, Elsevier, Vol 12, pp.349-370, 1995
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 a unweighted point set and the regular triangulation of a weighted point set. The algorithms run in expected time O(n log n) for unifirmly distributed points and other dense point sets. Worst case point sets, which do not occur very often in practice, require O(n^2) expected time. The software described in this paper is available via anonymous ftp at ftp.ncsa.uiuc.edu
Contact author(s) or publisher for availability and copyright information on above referenced article