Computational geometry may be used as a powerful tool for studying topology and architecture of macromolecules and macromolecular complexes. In this work the Delaunay tessellation is applied for the first time for the analysis of protein structure. By representing amino acid residues in protein chains by Ca atoms, the protein structure is described as a set of points in three- dimensional space. The Delaunay tessellation of a protein structure generates an aggregate of space-filling irregular tetrahedra, or Delaunay simplices. The vertices of each simplex define objectively four nearest neighbor Ca atoms, i.e. four nearest neighbor residues. A simplex classification scheme is introduced where simplices are divided into five classes based on the relative positions of vertex residues in protein primary sequence. The statistical analysis of residue composition of Delaunay simplices reveals nonrandom preferences for certain quadruplets of amino acids to be clustered together. This nonrandom preference may be used to develop a four-body potential that can be used in evaluating sequence-structure compatibility for the goals of inverted structure prediction. The residue composition of the simplices shows correlation with side-chain physical and chemical properties. The geometric characteristics of simplices (volume and tetrahedrality) correlate with relative positions of vertex residues in primary sequence and with the types of composing residues.