Modeling Macromolecular Complexes: A Journey Across Scales - Modeling in Computational Biology and Biomedicine - page 14

group radii [ 19 ], in which the atomic radii are slightly expanded to account for the
missing hydrogen atoms.) To handle different radii, the following generalization is
resorted to.
Consider a collection

{B i } i =1 ,...,n , each representing an atom. The
ball B i ( a i ,r i ) is centered at a i and has radius r i , and its bounding sphere is denoted
S i . The overall volume occupied by the n balls, also called the space-filling diagram
or simply molecule in our context, is defined by

S of n balls

F = ∪ i B i . To define the associated
Voronoı diagram, recall that the power distance from a point x with respect to the
sphere S i is defined by π ( x, S i )= || x − a i || 2 −r i . Denoting E 3 the usual three
dimensional Euclidean space, the Voronoı diagram of

S equipped with the power

distance consists of the Voronoı regions:

Vo r( S i )= {x ∈ E 3 such that π ( x, S i ) ≤ π ( x, S j ) , ∀S j = S i }. (1.1)

Note that the Voronoı cells partition the space into convex regions, each assigned
to one of the input balls, namely an atom in our case. The Voronoı diagram is an
example of cell complex , as it is made of cells (Voronoı regions, Voronoı faces,
Voronoı edges, and Voronoı vertices), which satisfy the following two conditions
(1) every face of a cell is also a face, and (2) the intersection of two cells is either
empty or a common face of both.

Delaunay diagram and privileged neighbors. The Delaunay diagram Del( S ) is
the dual of the Voronoı diagram, in the following sense. Whenever a collection of
k +1Voronoı cells have a non-empty intersection, that is,

∩ i∈I = {i 0 ,...,i k } Vo r ( S i ) = ∅, (1.2)

one reports the convex hull of the centers of the k +1balls defining these regions
into Del( S ). To fully understand this construction, recall that a geometric k -simplex
is the convex hull of k +1affinely independent points. For example, a 0-simplex
is a point, a 1-simplex is a line-segment, a 2-simplex is a triangle, a 3-simplex is a
tetrahedron, etc. Generically, that is if no four points are co-circular in 2D and no
five points co-spherical in 3D, the convex hull of the points involved in Eq. ( 1.2 )isa
k -simplex. Phrased differently, a k -simplex corresponds to the non-void intersection
of exactly k +1Voronoı regions, a property known as the Delaunay-Voronoı
duality. The terminology used to describe this duality in 3D is presented in Table 1.1 ,
and a 2D illustration is presented on Fig. 1.3 a.
The Voronoı or equivalently the Delaunay diagram of n balls in 3D has
quadratic O ( n 2 ) complexity in the worst-case, and can be computed in expected
O ( n log n + k ) time, with k the size of the output, that is the number of simplices
of the Delaunay triangulation [ 9 ]. This complexity, which depends on the size of the
output, is called output-sensitive .
Practically, elaborate algorithms have been designed to compute the Delaunay
triangulation, both from a combinatorial and a numerical standpoints—the latter
to make the computation robust to degeneracies and numerical rounding errors.