Molecular shape analysis based upon Morse-Smale complex and the connolly function

Docking is the process by which two or several molecules form a complex. Docking involves the geometry of the molecular surfaces, as well as chemical and energetic considerations. In the mid-eighties, Connolly proposed a docking algorithm matching surface knobs with surface depressions. We recast the notions of knob and depression of the Connolly function in the framework of Morse theory for functions defined over two-dimensional manifolds. First, we study the critical points of the Connolly function for smooth surfaces. Second, we provide an efficient algorithm for computing the Connolly function over a triangulated surface. Third, we introduce a Morse-Smale decomposition based on Forman s discrete Morse theory, and provide an O(n.log n) algorithm to construct it. This decomposition induces a partition of the surface into regions of homogeneous flow, and provides an elegant way to relate local quantities to global ones -from critical points to Euler characteristic of the surface. Fourth, we apply this Morse-Smale decomposition to the discrete gradient vector field induced by Connolly s function, and present experimental results for several mesh models.