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

作者：Yaffe Eitan^*; Halperin Dan

来源：Discrete & Computational Geometry, 2010, 44(3): 660-685.

DOI：10.1007/s00454-009-9240-9

Given a collection B of balls in a three-dimensional space, we wish to explore the cavities, voids, and tunnels in the complement space of boolean OR B. We introduce the pathway axis of B as a useful subset of the medial axis of the complement of boolean OR B and prove that it satisfies several desirable geometric properties. We present an algorithm that constructs the pathway graph of boolean OR B, a piecewise-linear approximation of the pathway axis. At the heart of our approach is an approximation scheme that constructs a collection kappa of same-size balls that approximate B so that the Hausdorff distance between boolean OR B and boolean OR kappa is bounded by a prescribed parameter. We prove a bound on the ratio between the number of balls in kappa and the number of balls in B. We employ this bound and the approximation scheme to show how to approximate the persistence diagrams for boolean OR B, which can be used to extract major topological features such as the large voids and tunnels in the complement of boolean OR B. We show that our approach is superior in terms of complexity to the standard point-sample approaches for the two problems that we address in this paper: approximating the pathway axis of B and approximating the persistence diagrams for boolean OR B. In a companion paper we introduce MolAxis, a tool for the identification of channels in macromolecules that demonstrates how the pathway graph and the persistence diagrams are used to identify plausible pathways in the complement of molecules.

• 出版日期2010-10