Computing elevation maxima by searching the gauss sphere
Article No.: 2.2, Pages 2.1 - 2.13
Abstract
The elevation function on a smoothly embedded 2-manifold in ℝ3 reflects the multiscale topography of cavities and protrusions as local maxima. The function has been useful in identifying coarse docking configurations for protein pairs. Transporting the concept from the smooth to the piecewise linear category, this article describes an algorithm for finding all local maxima. While its worst-case running time is the same as of the algorithm used in prior work, its performance in practice is orders of magnitudes superior. We cast light on this improvement by relating the running time to the total absolute Gaussian curvature of the 2-manifold.
References
[1]
Agarwal, P. K., Edelsbrunner, H., Harer, J., and Wang, Y. 2006. Extreme elevation on a 2-manifold. Discrete Comput. Geom. 36, 553--572.
[2]
Alboul, L. and Echeverria., G. 2005. Polyhedral Gauss maps and curvature characterization of triangle meshes. In Proceedings of the 11th IMA International Conference. Springer, Berlin, 14--33.
[3]
Banchoff, T. F. 1970. Critical points and curvature for embedded polyhedral surfaces. Am. Math. Mon. 77, 475--485.
[4]
Biogeometry. 2005. The biogeometry project. http://biogeometry.duke.edu/.
[5]
Cazals, F., Chazal, F., and Lewiner., T. 2003. Molecular shape analysis based upon the Morse-Smale complex and the connolly function. In Proceedings of the 19th Annual Symposium on Computational Geometry (SCG'03). ACM, New York, 351--360.
[6]
CGAL. 2011. Computational geometry algorithms library. http://www.cgal.org.
[7]
Cheng, H. L., Dey, T. K., Edelsbrunner, H., and Sullivan, J. 2001. Dynamic skin triangulation. Discrete Comput. Geom. 25, 525--568.
[8]
Cohen-Steiner, D., Edelsbrunner, H., and Harer., J. 2007. Stability of persistence diagrams. Discrete Comput. Geom. 37, 103--120.
[9]
Cohen-Steiner, D., Edelsbrunner, H., and Harer, J. 2009. Extending persistence using Poincaré and Lefschetz duality. Found. Comput. Math. 9, 79--103.
[10]
Cohen-Steiner, D. and Morvan, J. 2006. Second fundamental measure of geometric sets and local approximation of curvatures. J. Differ. Geom. 74, 3, 363--394.
[11]
Cole-McLaughlin, K., Edelsbrunner, H., Harer, J., Natarajan, V., and Pascucci, V. 2004. Loops in Reeb graphs of 2-manifolds. Discrete Comput. Geom. 32, 231--244.
[12]
Connolly, M. L. 1983. Analytic molecular surface calculation. J. Appl. Crystallog. 6, 548--558.
[13]
Connolly., M. L. 1986. Shape complementarity at the hemoglobin albl subunit interface. Biopolymers 25, 1229--1247.
[14]
de Berg, M., van Kreveld, M., Overmars, M., and Schwarzkopf, O. 1997. Computational Geometry - Algorithms and Applications. Springer-Verlag, Berlin.
[15]
Edelsbrunner, H. 1999. Deformable smooth surface design. Discrete Comput. Geom. 21, 87--115.
[16]
Edelsbrunner, H., Letscher, D., and Zomorodian, A. 2002. Topological persistence and simplification. Discrete Comput. Geom. 28, 511--533.
[17]
Georgiadis, L., Tarjan, R., and Werneck, R. F. 2006. Design of data structure for mergeable trees. In Proceedings of the 17th Annual ACM-SIAM Symposium Discrete Algorithms (SODA'06). ACM, New York, 394--403.
[18]
Morvan, J. 2008. Generalized Curvatures. Springer-Verlag, Berlin.
[19]
Munkres, J. R. 1984. Elements of Algebraic Topology. Addison-Wesley, Redwood City, CA.
[20]
Petterson, E. F., Goddard, T. D., Huang, C. C., Gouch, G. S., Greenblatt, D. M., Meng, E. C., and Ferrin, T. E. 2004. Ucsf chimera—a visualization system for exploratory research and analysis. J. Comput. Chem. 25, 1605--1612.
[21]
Sanner, M. F. and Olson, A. J. 1996. Reduced surface: an efficient way to compute molecular surfaces. Biopolymers 38, 305--320.
[22]
Santaló, L. 2004. Integral Geometry and Geometric Probability. Cambridge University Press, Cambridge, UK.
[23]
Wang, Y., Agarwal, P. K., Brown, P., Edelsbrunner, H., and Rudolph, J. 2005. Course and reliable geometric alignment for protein docking. In Proceedings of the Pacific Symposium on Biocomputing. Singapore, 64--75.
[24]
Welzl, E. 1991. Smallest enclosing disks (balls and ellipsoids). In Proceedings of the Symposium on New Results and New Trends in Computer Science. Springer, Berlin, 359--370.
[25]
Zomorodian, A. and Edelsbrunner, H. 2002. Fast software for box intersections. Int. J. Comput. Geom. Appl. 12, 143--172.
- Computing elevation maxima by searching the gauss sphere
Recommendations
Gauss map computation for free-form surfaces
The Gauss map of a smooth doubly-curved surface characterizes the range of variation of the surface normal as an area on the unit sphere. An algorithm to approximate the Gauss map boundary to any desired accuracy is presented, in the context of a tensor-...
Computing Elevation Maxima by Searching the Gauss Sphere
SEA '09: Proceedings of the 8th International Symposium on Experimental AlgorithmsThe elevation function on a smoothly embedded 2-manifold in ***3 reflects the multiscale topography of cavities and protrusions as local maxima. The function has been useful in identifying coarse docking configurations for protein pairs. Transporting ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © 2011 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 27 July 2011
Published in JEA Volume 16
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 145Total Downloads
- Downloads (Last 12 months)2
- Downloads (Last 6 weeks)0
Reflects downloads up to 11 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in