Approximating the pathway axis and the persistence diagram of a collection of balls in 3-space

ABSTRACT

Given a collection β of balls in three-dimensional space, each having a radius of at least 1, we present an approximation scheme that constructs a collection K_ε of unit balls that approximate β, such that the Hausdorff distance between ∪β and ∪K_ε is at most ε. We define the pathway axis as the subset of the medial axis of the complement of ∪β for which the set of closest balls in β do not have a common intersection. It is the medial axis of the complement of ∪β without `dead-ends' and therefore it is a good starting point for finding pathways that lie outside ∪β. The recently introduced persistence diagram of the distance function from ∪β 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 β. 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_ε, which can be easily and efficiently computed. We show that the pathway diagram contains an approximation of the pathway axis of β. We prove a bound on the ratio |K_ε|/|β|, namely the ratio between the number of unit balls in K_ε and the number of balls in β. We employ this bound to show how we efficiently approximate the persistence diagram of ∪β. 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 ∪β, and approximating the persistence diagram of ∪β. 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 are used to identify pathways in the complement of molecules.

REFERENCES

• 1: The CGAL Manaul, Release 3.2.1, 2006, http://www.cgal.org.
• 2: N. Amenta, S. Choi, and R. Kolluri. The power crust, unions of balls, and the medial axis transform. Computational Geometry: Theory and Applications, 19(2-3):127--153, 2001.
• 3: Dominique Attali , Jean-Daniel Boissonnat, A Linear Bound on the Complexity of the Delaunay Triangulation of Points on Polyhedral Surfaces, Discrete & Computational Geometry, v.31 n.3, p.369-384, February 2004 [doi>10.1007/s00454-003-2870-4]
• 4: D. Attali, J.-D. Boissonnat, and H. Edelsbrunner. Stability and computation of medial axes: A state of the art report. In B. H. T. Möller and B. Russell, editors, Mathematical Foundations of Scientific Visualization, Computer Graphics, and Massive Data Exploration. Springer-Verlag, Mathematics and Visualization, 2007.
• 5: Dominique Attali , Jean-Daniel Boissonnat , André Lieutier, Complexity of the delaunay triangulation of points on surfaces the smooth case, Proceedings of the nineteenth annual symposium on Computational geometry, June 08-10, 2003, San Diego, California, USA [doi>10.1145/777792.777823]
• 6: F. Aurenhammer and R. Klein. Voronoi diagrams. In J.-R. Sack and J. Urrutia, editors, Handbook of Computational Geometry, pages 201--290. Elsevier Science Publishers B.V. North-Holland, Amsterdam, 2000.
• 7: J.-D. Boissonnat and C. Delage. Convex hull and Voronoi diagram of additively weighted points. In Proceedings of the European Symposium on Algorithms, pages 367--378, 2005.
• 8: Jean-Daniel Boissonnat , Mariette Yvinec, Algorithmic geometry, Cambridge University Press, New York, NY, 1998
• 9: Gunnar Carlsson , Afra Zomorodian, The theory of multidimensional persistence, Proceedings of the twenty-third annual symposium on Computational geometry, June 06-08, 2007, Gyeongju, South Korea [doi>10.1145/1247069.1247105]
• 10: F. Chazal , A. Lieutier, Stability and homotopy of a subset of the medial axis, Proceedings of the ninth ACM symposium on Solid modeling and applications, June 09-11, 2004, Genoa, Italy
• 11: Frédéric Chazal , André Lieutier, The "λ-medial axis", Graphical Models, v.67 n.4, p.304-331, July 2005 [doi>10.1016/j.gmod.2005.01.002]
• 12: Frédéric Chazal , André Lieutier, Weak feature size and persistent homology: computing homology of solids in Rⁿ from noisy data samples, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy [doi>10.1145/1064092.1064132]
• 13: David Cohen-Steiner , Herbert Edelsbrunner , John Harer, Stability of persistence diagrams, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy [doi>10.1145/1064092.1064133]
• 14: T. K. F. Da and M. Yvinec. 3D Alpha Shapes. In cgal Editorial Board, editor, cgal- 3.2 User and Reference Manual. 2006. http://www.cgal.org/Manual/3.2/doc_html/cgal_manual/Alpha_shapes_3/Chapter_main.html.
• 15: Tamal K. Dey , Wulue Zhao, Approximate medial axis as a voronoi subcomplex, Proceedings of the seventh ACM symposium on Solid modeling and applications, June 17-21, 2002, Saarbrücken, Germany [doi>10.1145/566282.566333]
• 16: E. W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 1:269--271, 1959.
• 17: Herbert Edelsbrunner , M. J. Ablowitz , S. H. Davis , E. J. Hinch , A. Iserles , J. Ockendon , P. J. Olver, Geometry and Topology for Mesh Generation (Cambridge Monographs on Applied and Computational Mathematics), Cambridge University Press, New York, NY, 2006
• 18: Herbert Edelsbrunner , Michael Facello , Jie Liang, On the definition and the construction of pockets in macromolecules, Discrete Applied Mathematics, v.88 n.1-3, p.83-102, Nov. 9, 1998 [doi>10.1016/S0166-218X(98)00067-5]
• 19: H. Edelsbrunner, D. Letscher, and A. Zomorodian. Topological persistence and simplification. Discrete & Computational Geometry, 28(4):511--533, 2002.
• 20: Herbert Edelsbrunner , Ernst P. Mücke, Three-dimensional alpha shapes, ACM Transactions on Graphics (TOG), v.13 n.1, p.43-72, Jan. 1994 [doi>10.1145/174462.156635]
• 21: D. Freedman and C. Chen. Measuring and localing homology classes. The Computing Research Repository (CoRR), abs/0705.3061, 2007. http://arxiv.org/abs/0705.3061.
• 22: Joachim Giesen , Edgar A. Ramos , Bardia Sadri, Medial axis approximation and unstable flow complex, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA [doi>10.1145/1137856.1137905]
• 23: W. Humphrey, A. Dalke, and K. Schulten. VMD: Visual Molecular Dynamics. J. Mol Graphics, 14.1:33--38, 1996.
• 24: André Lieutier, Any open bounded subset of Rⁿ has the same homotopy type than its medial axis, Proceedings of the eighth ACM symposium on Solid modeling and applications, June 16-20, 2003, Seattle, Washington, USA [doi>10.1145/781606.781620]
• 25: J. Munkres. Elements of Algebraic Topology. Addison-Wesley, 1984.
• 26: J. D. Boissonnat , S. Oudot, Provably good surface sampling and approximation, Proceedings of the 2003 Eurographics/ACM SIGGRAPH symposium on Geometry processing, June 23-25, 2003, Aachen, Germany
• 27: E. W. Weisstein. Spherical code, from mathworld- a wolfram web resource, http://mathworld.wolfram.com/sphericalcode.html, 2000.
• 28: E. Yaffe. Efficient construction of pathways in the complement of the union of balls in R³. Master's thesis, Tel-Aviv University, September 2007. http://www.cs.tau.ac.il/~eitanyaf/thesis.pdf#.
• 29: E. Yaffe, D. Fishelovitch, H. J. Wolfson, R. Nussinov, and D. Halperin. MolAxis: Efficient and accurate identification of channels in macromolecules. To appear in PROTEINS : Structure, Function, and Bioinformatics.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
          Subjects: Approximation of surfaces and contours

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Geometric algorithms, languages, and systems; Curve, surface, solid, and object representations

General Terms:
Algorithms, Experimentation, Theory

Keywords:
alpha complex, medial axis, molecular modeling, persistence diagram