International
Tables for
Crystallography
Volume F
Crystallography of biological macromolecules
Edited by M. G. Rossmann and E. Arnold

© International Union of Crystallography 2006
International Tables for Crystallography (2006). Vol. F. ch. 22.1, p. 533   | 1 | 2 |

Section 22.1.1.2.3.3. `Chopping-down' method of finding vertices

M. Gersteina* and F. M. Richardsa

22.1.1.2.3.3. `Chopping-down' method of finding vertices

| top | pdf |

Because of vertex error and the complexities in locating vertices, a different algorithm has to be used for volume calculation with method B. (It can also be used with bisection.) First, surround the central atom (for which a volume is being calculated) by a very large, arbitrarily positioned tetrahedron. This is initially the `current polyhedron'. Next, sort all neighbouring atoms by distance from the central atom and go through them from nearest to farthest. For each neighbour, position a plane perpendicular to the vector connecting it to the central atom according to the predefined proportion (i.e. from the method B formulae or bisection). Since a Voronoi polyhedron is always convex, if any vertices of the current polyhedron are on the other side of this plane to the central atom, they cannot be part of the final polyhedron and should be discarded. After this has been done, the current polyhedron is recomputed using the plane to `chop it down'. This process is shown schematically in Fig. 22.1.1.4[link]. When it is finished, one has a list of vertices that can be traversed to calculate volumes, as in the basic Voronoi procedure.

[Figure 22.1.1.4]

Figure 22.1.1.4 | top | pdf |

The `chopping-down' method of polyhedra construction. This is necessary when using method B for plane positioning, since one can no longer solve for the position of vertices. One starts with a large tetrahedron around the central atom and then `chops it down' by removing vertices that are outside the plane formed by each neighbour. For instance, say vertex 0214 of the current polyhedron is outside the plane formed by neighbour 6. One needs to delete 0214 from the list of vertices and recompute the polyhedron using the new vertices formed from the intersection of the plane formed by neighbour 6 and the current polyhedron. Using the labelling conventions in Fig. 22.1.1.2[link], one finds that these new vertices are formed by the intersection of three lines (021, 024 and 014) with plane 06. Therefore one adds the new vertices 0216, 0246 and 0146 to the polyhedron. However, there is a snag: it is necessary to check whether any of the three lines are not also outside of the plane. To do this, when a vertex is deleted, all the lines forming it (e.g. 021, 024, 014) are pushed onto a secondary list. Then when another vertex is deleted, one checks whether any of its lines have already been deleted. If so, this line is not used to intersect with the new plane. This process is shown schematically in two dimensions. For the purposes of the calculations, it is useful to define a plane created by a vector v from the central atom to the neighbouring atom using a constant K so that for any point u on the plane [{\bf u} \cdot {\bf v} = K]. If [{\bf u} \cdot {\bf V} \gt K], u is on the wrong side of the plane, otherwise it is on the right side. A vertex point w satisfies the equations of three planes: [{\bf w} \cdot {\bf v}_{1} = K_{1}], [{\bf w} \cdot {\bf v}_{2} = K_{2}] and [{\bf w} \cdot {\bf v}_{3} = K_{3}]. These three equations can be solved to give the components of w. For example, the x component is given by [w_{x} = \pmatrix{K_{1} &v_{1y} &v_{1z}\cr K_{2} &v_{2y} &v_{2z}\cr K_{3} &v_{3y} &v_{3z}\cr} \Bigg/ \pmatrix{v_{1x} &v_{1y} &v_{1z}\cr v_{2x} &v_{2y} &v_{2z}\cr v_{3x} &v_{3y} &v_{3z}\cr}.]








































to end of page
to top of page