*(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.

download a PostScript version of the paper (1 MB)

June 15 1995