(1) The Scripps Research Institute, 10666 North Torrey Pines Road,
La Jolla, California 92037, USA.
(2) Université de Haute Alsace, Laboratoire MAGE, F.S.T., 4 rue des Frères Lumière,
Mulhouse 68093, France.
Proc. 11th ACM Symp. Comp. Geom., C6-C7, 1995.
In this paper we define the r-reduced surface of a set of n spheres representing a molecule in relation to the r-accessible and r-excluded surfaces. Algorithms are given to compute the outer component of the r-reduced surface in O[nlogn] operations and the analytical description of the corresponding r-excluded surface in time O[n]. An algorithm to handle the self-intersecting parts of that surface is described. These algorithms have been implemented in a program called MSMS, which was tested on a set of 709 proteins. The CPU time spent in the different algorithms composing MSMS are given for this set of molecules.