Above: Figure 1. Visualization of Almost-Delaunay Tetrahedra with threshold ε in the range 0 (red) < ε ≤ 0.35 (yellow) in acylphosphatase (PDB 2acy). Delaunay tetrahedra (ε=0) are not shown for clarity.

This package contains a C++ implementation in 3D of Almost-Delaunay simplices, a geometric framework for computing nearest neighbors for imprecise points described in the thesis work of Deepak Bandyopadhyay. The Delaunay tessellation is a geometric data structure that encodes the nearest neighbor relationships among a set of points in any dimension. The Delaunay tessellation has problems with imprecise points, such as protein structure coordinates determined from experiments or modeled theoretically; small perturbations in these coordinates may lead to widespread changes in the nearest neighbors reported. The Almost-Delaunay simplices aim to quantify this problem and offer an alternative data structure with a guarantee on nearest neighbors being stable to perturbations.

In 3D, Almost-Delaunay simplices (edges, triangles and tetrahedra) are pairs, triples and quadruples of points that can become neighbors in the Delaunay tessellation, in some configuration where all the points have moved from their initial positions by at most a distance ε. The minimum perturbation required for a particular simplex is denoted its *threshold*; this value is zero for a Delaunay simplex and otherwise is positive. The almost-Delaunay tetrahedra with threshold up to ε form a set AD(ε). The maximum perturbation allowed for any simplex (ε, above) is denoted the *cutoff*. The length of any edge in a simplex can be restricted to a maximum value, denoted the *edge length prune*. Pruning long edges avoids simplices along the convex hull of the point set that do not really represent neighboring points, and also takes into account the short range nature of protein interactions. Further details about the properties, algorithms and demonstrated uses of almost-Delaunay simplices can be found in a paper [Bandyopadhyay and Snoeyink, 2004] and on Deepak's almost-Delaunay project page.

This implementation of the almost-Delaunay simplices in C++ uses the CGAL library for robust geometric computation; it is described in detail in a CGAL workshop paper and on Deepak's software page. The implementation is specialized to 3D points since current applications are based on protein structures; the geometric framework is not restricted to a particular dimension, and fast algorithms for 2D and 3D are described in the paper. A 2D implementation in C++ is planned in the future, and would have many applications such as gel electrophoresis, cell counting and other problems that deal with nearest neighbors in imprecise 2D points. For now, a proof of concept MATLAB implementation in 2D is available from Deepak.

- Deepak Bandyopadhyay and Jack Snoeyink. "Almost Delaunay Simplices: Nearest Neighbor Relations for Imprecise Points". ACM-SIAM Symposium On Discrete Algorithms (SODA 2004), New Orleans, Jan 11-13, 2004, pp. 403-412.
- Deepak Bandyopadhyay and Jack Snoeyink. "Almost Delaunay Simplices: Robust Neighbor Relations for Imprecise 3D Points Using CGAL ". Second CGAL Workshop (held in conjunction with SCG 2004), New York, Jun 12, 2004.