SPHERES UNIONS AND INTERSECTIONS
ANALYTICAL COMPUTATION OF VAN DER WAALS SURFACES AND VOLUMES

© Michel Petitjean (retired since Jan 1st, 2023)

Author's most recent professional address:
INSERM ERL U1133 (BFA, CNRS UMR 8251), Université Paris Cité
35 rue Hélène Brion, 75205 Paris Cedex 13, France.

Formerly (2010-2018): MTi, INSERM UMR-S 973, Université Paris 7.
Formerly (2007-2009): CEA/DSV/iBiTec-S/SB2SM (CNRS URA 2096), Saclay, France.
Formerly (1987-2006): ITODYS, CNRS UMR 7086, Université Paris 7.

Contact: petitjean.chiral@gmail.com



Other topics:
The van der Waals solid is a simplified model of a molecule, such that each atom is represented by a hard sphere. The van der Waals surface is the surface of the union of the atomic spheres, and the van der Waals volume is the volume of this union of spheres. The analytical computation of this surface and volume is useful in theoretical chemistry and molecular modeling.

The analytical calculation of any union (or intersection) of spheres has been performed in the general case, for any set of spheres, discarding if the set has physical sense or not. The presentation of the calculation hereafter is simplified. The full theory is available in ref. [1], and [2] (more detailed).

The volume (or the surface) of the union of n spheres is an alternate sum of the volumes (or the surfaces) of their intersections, following the inclusion-exclusion principle:

V(1+2+...+n) = [V1+V2+...+Vn] - [V1,2+V1,3+...+Vn-1,n] + [V1,2,3+V1,2,4+...+Vn-2,n-1,n] +. .  .  . .  .  + (-1)n+1V1,2,...,n-1,n

It means that we need first to calculate the volume (or the surface) of any intersection of spheres.

The volume (or the surface) of the intersection of 2 spheres is trivial to compute. Considering the intersection of 3 spheres, we have 14 topological situations. Only one requires a non trivial calulation, the 13 others being solvable using the inclusion-exclusion principle (see figure 1 in the paper). The non trivial case of intersection is such that the intersection of the 3 spheres is partitioned into 3 parts, each one being delimited by the intersection of a dihedron and a sphere.

The two points tp and tm at the intersection of the surfaces of 3 spheres of radius R1, R2, R3, are of interest in trilateration.
Let dij be the distance between the centers ci and cj of the spheres i and j.
The surface S of the triangle c1,c2,c3 is such that
16S2 = (d12+d23+d31)(-d12+d23+d31)(d12-d23+d31)(d12+d23-d31)
The midpoint t=(tp+tm)/2 is in the plane of the centers: t=(a1c1+a2c2+a3c3)/16S2
ai = Ri2(-2djk2) + Rj2(djk2+dki2-dij2) + Rk2(djk2-dki2+dij2) + djk2(-djk2+dki2+dij2)
where i,j,k are circular permutations of 1,2,3.
The three quantities ai/16S2 (i=1,2,3) are the barycentric coordinates of t in the triangle and their sum is 1.
When ai is negative, t is outside the triangle, separated from ci by the segment cj-ck.
Setting g=(c1+c2+c3)/3, the square of the length of the segment [tp-t] is
d2(tp,t) = d2(tm,t) = (R12+R22+R32)/3 - d2(t,g) - (d122+d232+d312)/9
The condition of existence of the two intersection points is that d2(tp,t) must be non negative.

Then comes the use of the Gauss-Bonnet theorem (see any textbook on differential geometry). This theorem relates the surface integral to integrals along the curves bounding the surface. Fortunately, these lines are here arcs of circle, such that the surface is computable analytically. The volume is computed by analytical integration of the surface.

Considering now the intersections of 4 spheres, we have in fact only one non trivial situation, the others being solved from the knowledge of 3-order intersections. The non trivial intersection is partitioned into 4 parts, each one being delimited by the intersection of a trihedron and a sphere. Calculating analytically the surface of each spherical triangle is easily done with the Gauss-Bonnet theorem, because the boundaries of the spherical triangles are arcs of circles. The volume of each intersection between a sphere and a trihedron is computed by analytical integration of the spherical triangular surface bounding the intersection. Note that the origin of the trihedron is not, in general, the center of the sphere. Note also that the general situation of the 3-order intersection may be treated as 6 intersections sphere-trihedron.

The intersections of more than 4 spheres are handled via the three-spheres theorem (see appendix 4 in [1] or theorem 4.5 in [2]):
Let n spheres have a common nonempty intersection. When n>4, there is at most m=3 spheres such that the intersection I of the n-m remaining spheres is included in the union J of the m spheres.
A major consequence of this theorem is that, applying the inclusion-exclusion principle to both members of the equality  I U J = J provides a relation between the n-order intersection and the (n-1)-order intersections. Starting from 4-order intersections, we thus get all higher order intersections, both for surfaces and volumes. Moreover, using Helly's theorem [3], the list of existing intersections of any order greater than 4 is generated from the list of 4-order intersections, because spheres are convex sets.
The three-spheres theorem theorem has analogs in dimension d=1 and dimension d=2, and is conjectured to have analogs in dimensions d>3: see theorem 4.6 in [2], a stronger version of the latter.

Computing the 4-order intersections is thus the basic task to compute all required intersections and unions of spheres.

The freeware ASV computes analytically the surface and volume of any union of spheres, even if it makes no physical sense (input data can be read following some of the usual formats encountered in chemistry).

Generalization in the d-dimensional space:
We have solved the three dimensional case, and the bidimensional case is easy to solve (lengths and surfaces of unions and intersections of circles in the plane). The generalization to d-spheres would require the knowledge of analogs of the Gauss-Bonnet theorem in dimension greater than 3. Unfortunately, such analogs seem to be unknown.



REFERENCES


  1. PETITJEAN M.
    On the Analytical Calculation of van der Waals Surfaces and Volumes: Some Numerical Aspects.
    J. Comput. Chem. 1994,15[5],507-523.
    (DOI 10.1002/jcc.540150504)
    Free version for readers: https://rdcu.be/bz18T (link created by Wiley; downloads, prints and copies are for subscribers only)

    2.
  2. PETITJEAN M.
    Spheres Unions and Intersections and Some of their Applications in Molecular Modeling.
    (DOI 10.1007/978-1-4614-5128-0_4)
    In: Distance Geometry: Theory, Methods, and Applications, chap. 4, pp. 61-83.
    Mucherino, A.; Lavor, C.; Liberti, L.; Maculan, N. (Eds.), Springer, 2013.
    ISBN 978-1-4614-5127-3
    Download a free preprint from the HAL repository: hal-01955983

  3. EDELSBRUNNER H.
    Algorithms in Combinatorial Geometry. EATCS Monographs on Theoretical Computer Science, volume 10, p.65
    W.Brauer, G.Rozenberg and A.Salomaa Eds., Springer-Verlag, Berlin 1987.