Spheres, molecules, and hidden surface removal

ABSTRACT

We devise techniques to manipulate a collection of loosely interpenetrating spheres in three-dimensional space. Our study is motivated by the representation and manipulation of molecular configurations, modeled by a collection of spheres. We analyze the sphere model and point to its favorable properties that make it more easy to manipulate than an arbitrary collection of spheres. For this special sphere model we present efficient algorithms for computing its union boundary and for hidden surface removal. The efficiency and practicality of our approach are demonstrated by experiments on actual protein data.

REFERENCES

• 1: E.E. Abola, F.C. Bernstein, S.H. Bryant, T.F. Koetzle and J. Weng, Protein data bank, in Crystallographic Databases: Information Content, Software Systems, Scientific Applications, F.H. Allen, G. Bergerhoff and R. Seivers, Eds., Data Comission of the International Union of Crystallography, Bonn/Cambridge/Chester, 1987, pp. 107-132.
• 2: F.C. Bernstein, T.F. Koetzle, G.J.B. Williams, E.F. Meyer Jr., M.D. Brice, J.R. Rodgers, O. Kennard, T. Shimanouchi and M. Tasumi, The protein data bank: A computer-b~$cd e~rchlvM lql~ for m~cromol~cul~r structure, Journal of Molecular Biology 112 (1{}77), pp. 535-542.
• 3: Bernard Chazelle , Herbert Edelsbrunner , Leonidas J. Guibas , Micha Sharir, A singly exponential stratification scheme for real semi-algebraic varieties and its applications, Theoretical Computer Science, v.84 n.1, p.77-105, July 22, 1991 [doi>10.1016/0304-3975(91)90261-Y]
• 4: Kenneth L. Clarkson , Herbert Edelsbrunner , Leonidas J. Guibas , Micha Sharir , Emo Welzl, Combinatorial complexity bounds for arrangements of curves and spheres, Discrete & Computational Geometry, v.5 n.2, p.99-160, 1990 [doi>10.1007/BF02187783]
• 5: M.L. Connolly, Solvent-accessible surfaces of proteins and nucleic acids, Science 221 (1983), pp. 709-713.
• 6: Mark de Berg, Ray Shooting, Depth Orders and Hidden Surface Removal, Springer-Verlag New York, Inc., Secaucus, NJ, 1993
• 7: M. Dietzfelbinger, A. Karlin, K. Mehlhorn, F. Meyer auf der Heide, H. Rohnert and R.E. Tarjan, Dynamic perfect hashing: upper and lower bounds, Proc. 29th IEEE Symposium on Foundations of Computer Science, 1988, pp. 524-531.
• 8: P.-O. Fj'gllstrSm and j. Petersson, Evaluation of algorithms for geometrical contact-searching problems, manuscript, 1993.
• 9: G-J. Giezeman and M.H. Overmars, Fast display of molecular models, in preparation.
• 10: Leonidas Guibas , Jorge Stolfi, Primitives for the manipulation of general subdivisions and the computation of Voronoi, ACM Transactions on Graphics (TOG), v.4 n.2, p.74-123, April 1985 [doi>10.1145/282918.282923]
• 11: Handbook of Biochem,stry, H.A. Sober, Editor, The Chemical Rubber Co., 2nd Edition, 1970.
• 12: Matthew J. Katz , Mark H. Overmars , Micha Sharir, Efficient hidden surface removal for objects with small union size, Computational Geometry: Theory and Applications, v.2 n.4, p.223-234, Dec. 1992 [doi>10.1016/0925-7721(92)90024-M]
• 13: Klara Kedem , Ron Livne , János Pach , Micha Sharir, On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles, Discrete & Computational Geometry, v.1 n.1, p.59-71, 1986 [doi>10.1007/BF02187683]
• 14: B. Lee and F.M. Richards, The interpretation of protein structure: Estimation of static accessibility, J. of Molecular Biology 55 (1971) pp. 379-400.
• 15: Jiří Matoušek , Nathaly Miller , Micha Sharir , Shmuel Sifrony , János Pach , Emo Welzl, Fat triangles determine linearly many holes, Proceedings of the 32nd annual symposium on Foundations of computer science, p.49-58, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185347]
• 16: P.G. Mezey, Molecular surfaces, in Reviews in Computational Chemistry, Vol. I, K.B. Lipkowitz and D.B. Boyd, Eds., VCH Publishers, 1990.
• 17: Mark H. Overmars, Point location in fat subdivisions, Information Processing Letters, v.44 n.5, p.261-265, Dec. 21, 1992 [doi>10.1016/0020-0190(92)90211-D]
• 18: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 19: M. Sharir, Almost tight upper bounds for lower envalopas in higher dimensions, P,~oc. 9~ tk A .... IRtiYR Sympos. Found. Comput. Sci., 1993, pp. 498-507.
• 20: A. Frank van der Stappen , Dan Halperin , Mark H. Overmars, The complexity of the free space for a robot moving amidst fat obstacles, Computational Geometry: Theory and Applications, v.3 n.6, p.353-373, Dec. 1993 [doi>10.1016/0925-7721(93)90007-S]
• 21: Amitabh Varshney , Frederick P. Brooks, Fast analytical computation of Richards's smooth molecular surface, Proceedings of the 4th conference on Visualization '93, October 25-29, 1993, San Jose, California

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Visible line/surface algorithms

  J. Computer Applications
  J.3 LIFE AND MEDICAL SCIENCES
      Subjects: Biology and genetics

General Terms:
Algorithms, Theory, Verification