Abstract. This paper presents detri 2.2, an implementation for Delaunay triangulations of three-dimensional point sets. The code uses a variant of the randomized incremental-flip algorithm, and employs a symbolic perturbation scheme to achieve robustness. The algorithm's time complexity is quadratic in n, the number of input points, and this is optimal in the worst case. However, empirically, we can expect running times roughly proportional to the number of triangles in the final triangulation, which typically is linear in n. Even though the symbolic perturbation scheme relies on exact arithmetic, the resulting code is efficient in practice. This is mainly due to a careful implementation of the geometric primitives and the arithmetic module. The source code is available on the Internet.

Postscript [135k] of April 12, 1995

Suggested BIBTeX entry:

@inproceedings{LABEL
,author=        "M{\"u}cke, E. P."
,title=         "A Robust Implementation for
		Three-dimensional Delaunay Triangulations"
,booktitle=	"Proceedings of the 1st International
		Computational Geometry Software Workshop"
,year=		1995
,pages=		"70--73"
,note=		"To appear in the {\it International Journal of
                Computational Geometry \& Applications}"
,url=           "http://www.geom.umn.edu/locate/cglist/GeomDir/detri95.html"
}