Proceedings of the 25th annual symposium on Computational geometry - SCG '09
Full text: Download
We describe a new implementation of the well-known incre- mental algorithm for constructing Delaunay triangulations in any dimension. Our implementation follows the exact computing paradigm and is fully robust. Extensive compar- isons show that our implementation outperforms the best currently available codes for exact convex hulls and Delau- nay triangulations, compares very well to the fast non-exact Qhull implementation and can be used for quite big input sets in spaces of dimensions up to 6. To circumvent pro- hibitive memory usage, we also propose a modification of the algorithm that uses and stores only the Delaunay graph (the edges of the full triangulation). We show that a careful implementation of the modified algorithm performs only 6 to 8 times slower than the original algorithm while drasti- cally reducing memory usage in dimension 4 or above.