A statistical geometry approach to study structure of molecular systems was pioneered by John Bernal, who in the late 1950s suggested that ''many of the properties of liquids can be most readily appreciated in terms of the packing of irregular polyhedra'' (Bernal, 1959). Bernal pointed out that ''it would be most desirable to find the true minimum number of parameters or parametral functions defining the statistical structure of any homogenous irregular assemblage in the way that the lattice vectors define a regular one'' (Bernal, 1959). Methods of computational geometry, Voronoi and Delaunay tessellations in particular, may be used to address this problem. This approach, based on the Voronoi partitioning of space (Voronoi, 1908) occupied by the molecule, was further developed by Finney for liquid and glass studies (Finney, 1970). Finney proposed a set of ''descriptive parameters'' for packing of polyhedra in simple liquids. In the mid-1970s the statistical geometry approach was first applied to study packing and volume distributions in proteins by Richards (1974), Chothia (1975) and Finney (1975).
Richards applied Voronoi tessellation to calculate atomic volumes in the experimentally solved crystallographic structures of ribonulease C and lysozyme (Richards, 1974) and Chothia extended the calculations to a larger set of proteins (Chothia, 1975). Standard Voronoi tessellation algorithm treats all atoms as points and allocates volume to each atom regardless of the atom size, which leads to the volume overestimate for the small atoms and underestimate for the large ones. Richards introduced changes in the algorithm (Richards, 1974) that made Voronoi volumes proportional to the atom sizes, creating chemically more relevant partitioning, however it has been done at the expense of the robustness of the algorithm. The Voronoi polyhedra in this case do not fill all available space. In addition to polyhedra around the atoms Richards' method produces so called vertex polyhedra in the unallocated volumes in the neighborhood of each vertex. As a result the accuracy of the tessellation is reduced. An alternative procedure, the ''radical plane'' partitioning, which is both chemically appropriate and completely rigorous was designed by Gellatly and Finney (1982) and applied to the calculation of protein volumes. The radical plane of two spheres is the locus of points from which the tangent lengths to both spheres are equal. Using the three-dimensional structure of RNAase-C as an example, they have shown that the differences between the results from the radical plane and Richards' methods are generally smaller than the difference between either of those and Voronoi's method. Both radical plane and Richards' methods are relatively insensitive to the treatment of surface, which makes them preferential to other techniques (Gellatly and Finney, 1982). Volume calculation remains one of the most popular applications of Voronoi tessellation to protein structure analysis. It has been used to evaluate the differences in amino acid residue volumes in solution and in the interior of folded proteins (Harpaz et al., 1994), to monitor the atomic volumes in the course of molecular dynamics simulation of a protein (Gerstein et al., 1995), to compare the sizes of atomic groups in proteins and organic compounds (Tsai et al., 1999), to calculate the atomic volumes on protein-protein interfaces (Lo Conte et al., 1999), and to measure sensitivity of residue volumes to the selection of tessellation parameters and protein training set (Tsai and Gerstein, 2002). Deviations from standard atomic volumes in proteins determined through Voronoi tessellation correlate with crystallographic resolution and can be used as a quality measure for crystal structures (Pontius et al., 1996). A modified Voronoi algorithm, where dividing planes between the atoms were replaced by curved surfaces, defined as the set of geometrical loci with equal orthogonal distance to the surfaces of the respective van der Waals spheres, was proposed by Goede et al. (1997). Voronoi cells with hyperbolic surface constructed by this algorithm improve the accuracy of volume and density calculations in proteins (Rother et al., 2003). Another extension of the Voronoi algorithm, the Laguerre polyhedral decomposition was applied to the analysis of the residue packing geometry (Sadoc et al., 2003).
One of the problems in constructing Voronoi diagram for the molecular systems is related to the difficulty of defining a closed polyhedron around the surface atoms, which leads to ambiguities in determining their volumes and densities (a recent example in Quillin and Matthews, 2000). This problem can be addressed by the ''solvation'' of the tessellated molecule in the at least one layer of solvent or by using computed solvent-accessible surface for the external closures of Voronoi polyhedra. The analysis of atomic volumes on the protein surface can be used to adjust parameters of the force field for implicit solvent models, where the solvent is represented by the generalized Born model of electrostatic salvation which require knowledge of the volume of individual solute atoms (Schaefer et al., 2001). Interactions between residues in proteins can be measured using the contact area between atoms defined as the area of intersection of the van der Waals sphere and the Voronoi polyhedron of an atom (Wernisch et al., 1999). Examining the packing of residues in proteins by Voronoi tessellation revealed a strong fivefold local symmetry similar to random packing of hard spheres, suggesting a condensed matter character of folded proteins (Soyer et al., 2000). Correlations between the geometrical parameters of Voronoi cells around residues and residue conformations were discovered by Angelov et al. (2002). Another recent study described application of Voronoi procedure to study atom-atom contacts in proteins (McConkey et al., 2002).
A topological dual to Voronoi partitioning, the Delaunay tessellation (Delaunay, 1934) has an additional utility as a method for non-arbitrary identification of neighboring points in the molecular systems represented by the extended sets of points in space. Originally the Delaunay tessellation has been applied to study model (Voloshin et al., 1989) and simple (Medvedev and Naberukhin, 1987) liquids, as well as water (Vaisman et al., 1993) and aqueous solutions (Vaisman and Berkowitz, 1992; Vaisman et al., 1994). The Delaunay tessellation proved to be a particularly convenient and efficient descriptor of water structure, where a natural tetrahedral arrangement of molecules is present in the first hydration shell (Vaisman et al., 1993).
The first application of the Delaunay tessellation for identification of nearest neighbor residues in proteins and derivation of a four-body statistical potential was developed in the mid-1990s (Singh et al., 1996). This potential has been successfully tested for inverse protein folding (Tropsha et al., 1996), fold recognition (Zheng et al., 1997), decoy structure discrimination (Munson et al., 1997; Krishnamoorthy and Tropsha, 2003), protein design (Weberndorfer et al., 1999), protein folding on a lattice (Gan et al., 2001), mutant stability studies (Carter et al., 2001), computational mutagenesis (Masso and Vaisman, 2003), protein structure similarity comparison (Bostick and Vaisman, 2003), and protein structure classification (Bostick et al., 2004). Statistical compositional analysis of Delaunay simplices revealed highly nonrandom clustering of amino acid residues in folded proteins when all residues were treated separately as well as when they were grouped according to their chemical, structural, or genetic properties (Vaisman et al., 1998). A Delaunay tessellation based alpha-shape procedure for protein structure analysis was developed by Liang et al. (Liang et al., 1998a). Alpha shapes are polytopes that represent generalizations of the convex hull. A real parameter alpha defines the ''resolution'' of the shape of a point set (Edelsbrunner et al., 1983). Alpha shapes proved to be useful for the detection of cavities and pockets in protein structures (Liang et al., 1998b; 1998c). Several alternative Delaunay and Voronoi based techniques for cavity identification were described by Richards (1985), Bakowies and van Gunsteren (2002) and Chakravarty et al. (2002). Delaunay tessellation has been also applied to compare similarity of protein local substructures (Kobayashi and Go, 1997) and to study the mechanical response of a protein under applied pressure (Kobayashi et al., 1997).