Dissemin is shutting down on January 1st, 2025

Published in

Proceedings of the nineteenth conference on Computational geometry - SCG '03

DOI: 10.1145/777792.777845

Proceedings of the nineteenth conference on Computational geometry - SCG '03

DOI: 10.1145/777842.777845

Links

Tools

Export citation

Search in Google Scholar

Molecular shape analysis based upon the morse-smale complex and the connolly function

Proceedings article published in 2003 by F. Cazals ORCID, F. Chazal, T. Lewiner
This paper is available in a repository.
This paper is available in a repository.

Full text: Download

Green circle
Preprint: archiving allowed
Green circle
Postprint: archiving allowed
Red circle
Published version: archiving forbidden
Data provided by SHERPA/RoMEO

Abstract

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 energetical considerations. In the mid-eighties, Connolly proposed a docking algorithm matching surface {\em knobs} with surface {\em depressions}. Knobs and depressions refer to the extrema of the {\em Connolly} function, which is defined as follows. Given a surface $\calM$ bounding a three-dimensional domain $X$, and a sphere $S$ centered at a point $p$ of $\calM$, the Connolly function is equal to the solid angle of the portion of $S$ containing within $X$. 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's 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.