Tunnels and Voids in Molecules via Voronoi Diagrams and Beta-complexes

Abstract

Molecular external structure is important in understanding molecular interaction with its solvent environment and is useful in developing drugs. Important examples of external structures are tunnels, pockets, caves, clefts, voids, etc. This paper presents algorithms to extract tunnels and voids from molecular structures. The algorithms are based on the the Voronoi diagram of atoms in molecules and their time complexity are both O(m) time in the worst case, where m represents the number of entities in the Voronoi diagram. The algorithms are mathematically correct, computationally efficient, numerically robust, and easy to implement.