Approximating the Pathway Axis and the Persistence Diagram of a Collection of Balls in 3-Space

Given a collection B of balls in three-dimensional space, each having a radius of at least 1, we present an approximation scheme that constructs a collection K-epsilon, of unit balls that approximate B, such that the Hausdorff distance between UB and UK epsilon is at most epsilon. We define the pathway axis as the subset of the medial axis of the complement of UB for which the set of closest balls in B do not have a common intersection. It is the medial axis of the complement of US without 'dead-ends' and therefore it is a good starting point for finding pathways that lie outside UB. The recently introduced persistence diagram of the distance function from UB encodes topological characteristics of the function, giving a measure on the importance of topological features such as voids or tunnels during a uniform growth process of B. In this paper we introduce the pathway diagram as a useful subset of the Voronoi diagram of the centers of the unit balls in K-epsilon, which can be easily and efficiently computed. We show that the pathway diagram contains an approximation of the pathway axis of B. We prove a bound on the ratio vertical bar K-epsilon vertical bar/vertical bar B vertical bar, namely the ratio between the number of unit balls in K-epsilon and the number of balls in B. We employ this bound to show how we efficiently approximate the persistence diagram of UB. Finally, we show that our approach is superior to the standard point-sample approaches for the two problems that we address in this paper: Approximating the medial axis of the complement of UB, and approximating the persistence diagram of UB. In a companion paper we introduce MolAxis, a tool for the identification of channels in macromolecules, that demonstrates how the pathway diagram and the persistence diagram axe used to identify pathways in the complement of molecules.