Molecular surface is an important example of molecular structure. Given a molecular surface, the area and volume of the molecule can be computed to facilitate problems such as protein docking and folding. Therefore, it is important to compute a molecular surface precisely and efficiently.

This paper presents an algorithm for correctly and efficiently computing the blending surfaces of a protein which is an important part of the molecular surface. Assuming that the Voronoi diagram of atoms of a protein is given, we first compute the \beta-shape of the protein corresponding to a solvent probe. Then, we use a search space reduction technique for the intersection tests while the link blending surface is computed. Once a ?-shape is obtained, the blending surfaces corresponding to a given solvent probe can be computed in O(n) in the worst case, where n is the number of atoms. The correctness and efficiency of the algorithm stem from the powerful properties of \beta-shape, quasitriangulation, and the interworld data structure.