Computing a Pocket Depth Descriptor for Bio-Molecules

We consider the following problem. Given a simple polytope S in R³, with a total of n edges, and a query point s on S, find a shortest path from s to the boundary of the convex hull, CH(S), of S, that does not go through the interior of S. The problem has applications in structural proteomics in the computation of shape descriptors. Specifically, if s is a point on the surface S of a protein P and s is within a pocket of P, finding the pocket depth of s reduces to this problem. Our main contribution is to show how to extend two point-to-point approximation algorithms proposed by Papadimitriou and Har-Peled to solve the point-to-face version of the shortest path problem proposed in this paper.