Delaunay simplices

Figure 10.3 Illustration of Voronoi/Delaunay tessellation in 2D space (Voronoi polyhedra are represented by dashed lines, and Delaunay simplices by solid lines). For the collection of points with 3D coordinates, such as atoms of the protein-ligand complex, Delaunay simplices are tetrahedra whose vertices correspond to the atoms.

The Voronoi tessellation divides space into polyhedral regions that are closer to the center of a given particle than to any other. Joining pairs of particle centers whose Voronoi polyhedra share a face yields a dual tessellation of space into Delaunay simplices. 

To define a local subset of Pareto-optimal solutions dose to y the Delaunay triangulation is calculated for the set Z = ZHf u y. The Delaunay triangidation subdivides the convex hull of a set of points into disjunct simplices. Each simplex consists of d + points whereby d denotes the dimension of the data set. A specific property of the Delaunay triangulation is that for each simplex the circumhypersphere constituted by its points is empty which implies that the Delaunay triangulation is unique. Let D denote the set of Delaunay simplices where each simplex Ak is a set of d+1 points, i.e.di,= ... 

N. N. Medvedev, Y. I. Naberukhin, Shape of the Delaunay simplices in dense random packings of hard and soft spheres, J. Non-Cryst. Solids 94 (1987) 402-406. 

Delaunay triangulation maximizes the minimum angle of all simplices. Alternatively, the procedure could be briefly described as finding all adjacent points off in the Delaunay graph. 

---