Computing Elevation Maxima by Searching the Gauss Sphere
| JEA: | ACM Journal of Experimental Algorithmics, vol. 16, pages 1-13, 2011. |
| SEA2009: | Proceedings of the International Symposium on Experimental Algorithms, Lecture Notes in Computer Science 5526, pages 281-292, 2009. |
|
SEA 2009 |
Abstract
The elevation function on a smoothly embedded 2-manifold in R3 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 paper 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.
The elevation function on a smoothly embedded 2-manifold in R3 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 paper 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
[4]
P. K. Agarwal, H. Edelsbrunner, J. Harer and Y. Wang. Extreme elevation on a 2-manifold. Discrete and Computational Geometry. 36 (2006), 553–572.