A Comparison of Five Implementations of 3D Delaunay Tessellation
Yuanxin Liu, Jack Scott Snoeyink · 2005
When implementing Delaunay tessellation in 3D, a number of engineering decisions must be made about update and location algorithms, arithmetics, perturbations, and representations. We compare five codes for computing 3D Delaunay tessellation: qhull, hull, CGAL, pyramid, and our own tess3, and explore experimentally how these decisions affect the correctness and speed of computation, particularly for input points that represent atoms coordinates in proteins. 1. Introduction The Delaunay tessellation is a useful canonical decomposition of the space around a given set of points in a Euclidean space E 3 , frequently used for surface reconstruction, molecular modelling and tessellating solid shapes [Delaunay 1934; Boissonnat and Yvinec 1998; Okabe et al. 1992]. The Delaunay tessellation is often used to compute its dual Voronoi diagram, which captures proximity. In its turn, it is often computed as a convex hull of points lifted to the paraboloid of revolution in one dimension higher [Brown 1979; Brown 1980]. As we sketch in this paper, there are a number of engineering decisions that must be made by implementors, including the type of arithmetic, degeneracy handling, data structure representation, and low-level algorithms. We wanted to know what algorithm would be fastest for a particular application: computing the Delaunay tessellation of points that represent atoms coordinates in proteins, as represented in the PDB (Protein Data Bank) format [Berman et al. 2000]. Atoms in proteins are well-packed, so points from PDB files tend to be evenly distributed, with physically-enforced minimum separation distances. Coordinates in PDB files have a limit on precision: because they have an 8.3f field specification in units of angstroms, they may have three decimal digits before the decimal place (four if the number is positive), and three digits after.