Windows (any STL-compliant compiler; tested on MS VC++ .NET 2003 and the Intel compiler; Cygwin gcc compilation is temporarily broken) Linux (g++-3.2 or higher)
Source: zipped) (684k unzipped) Linux binaries: Linux/ADCGAL (4.24MB) Linux/ADedgeCGAL (4.14MB) Windows binaries: Windows/ADCGAL (614k) Windows/ADedgeCGAL (528k) Binaries are distributed separately, in two versions: ADCGAL that computes edges, triangles and tetrahedra, and ADedgeCGAL that computes only edges. Linux binaries are much larger since they are packaged with static libraries so that they work seamlessly across different Linux systems where the dynamic libraries are stored in different places.
AlmDel software was featured in BioGeometry News, June 2005 issue (pdf).

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.