Approximating the pathway axis and the persistence diagrams for a collection of balls in 3-space. (English) Zbl 1211.52004

Summary: Given a collection \(\mathcal B\) of balls in a three-dimensional space, we wish to explore the cavities, voids, and tunnels in the complement space of \(\cup \mathcal B\). We introduce the pathway axis of \(\mathcal B\) as a useful subset of the medial axis of the complement of \(\cup \mathcal B\) and prove that it satisfies several desirable geometric properties. We present an algorithm that constructs the pathway graph of \(\cup \mathcal B\), a piecewise-linear approximation of the pathway axis. At the heart of our approach is an approximation scheme that constructs a collection \({\mathcal{K}}\) of same-size balls that approximate \(\mathcal B\) so that the Hausdorff distance between \(\cup \mathcal B\) and \(\cup{\mathcal{K}}\) is bounded by a prescribed parameter. We prove a bound on the ratio between the number of balls in \({\mathcal{K}}\) and the number of balls in \(\mathcal B\). We employ this bound and the approximation scheme to show how to approximate the persistence diagrams for \(\cup \mathcal B\), which can be used to extract major topological features such as the large voids and tunnels in the complement of \(\cup \mathcal 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 \(\mathcal B\) and approximating the persistence diagrams for \(\cup \mathcal B\). In a companion paper [E. Yaffe, D. Fishelovitch, H. J. Wolfson, D. Halperin, and R. Nussinov, Bioinform. 73.1, 72–86 (2008)], we introduced 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.


52A15 Convex sets in \(3\) dimensions (including convex surfaces)
05C90 Applications of graph theory
52C45 Combinatorial complexity of geometric structures
52B55 Computational aspects related to convexity
92E10 Molecular structure (graph-theoretic methods, methods of differential topology, etc.)
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
65D18 Numerical aspects of computer graphics, image analysis, and computational geometry
Full Text: DOI


[1] Amenta, N.; Choi, S.; Kolluri, R., The power crust, unions of balls, and the medial axis transform, Comput. Geom. Theory Appl., 19, 127-153, (2001) · Zbl 0988.65015
[2] Attali, D.; Boissonnat, J.-D., A linear bound on the complexity of the Delaunay triangulation of points on polyhedral surfaces, Discrete Comput. Geom., 31, 369-384, (2004) · Zbl 1063.68100
[3] Attali, D.; Boissonnat, J.-D.; Edelsbrunner, H.; Möller, B. H.T. (ed.); Russell, B. (ed.), Stability and computation of medial axes: A state of the art report, (2007), Berlin
[4] Attali, D., Boissonnat, J.-D., Lieutier, A.: Complexity of the Delaunay triangulation of points on surfaces: The smooth case. In: Proceedings of the Symposium on Computational Geometry, pp. 201-210 (2003) · Zbl 1374.68638
[5] Aurenhammer, F.; Klein, R.; Sack, J.-R. (ed.); Urrutia, J. (ed.), Voronoi diagrams, 201-290, (2000), Amsterdam · Zbl 0995.65024
[6] Boissonnat, J.-D., Delage, C.: Convex hull and Voronoi diagram of additively weighted points. In: Proceedings of the European Symposium on Algorithms, pp. 367-378 (2005) · Zbl 1162.68736
[7] Boissonnat, J.-D.; Oudot, S., Provably good sampling and meshing of surfaces, Graph. Models, 67, 405-451, (2005) · Zbl 1087.68114
[8] Boissonnat, J.-D., Yvinec, M.: Algorithmic Geometry. Cambridge University Press, Cambridge (1998). Translated from the French version by H. Brönnimann · Zbl 0917.68212
[9] Carlsson, G., Zomorodian, A.: The theory of multidimensional persistence. In: Proceedings of the Symposium on Computational Geometry, pp. 184-193 (2007) · Zbl 1188.55001
[10] Chazal, F., Lieutier, A.: Stability and homotopy of a subset of the medial axis. In: Proceedings of the Symposium on Solid Modeling and Applications, pp. 243-248 (2004)
[11] Chazal, F.; Lieutier, A., The “Lambda-medial axis”, Graph. Models, 67, 304-331, (2005) · Zbl 1175.68487
[12] Chazal, F., Lieutier, A.: Weak feature size and persistent homology: Computing homology of solids in ℝ \(n\) from noisy data samples. In: Proceedings of the Symposium on Computational Geometry, pp. 255-262 (2005) · Zbl 1380.68388
[13] Chazal, F., Oudot, S.: Towards persistence-based reconstruction in Euclidean spaces. In: Proceedings of the Symposium on Computational Geometry, pp. 232-241 (2008) · Zbl 1271.57058
[14] Cohen-Steiner, D.; Edelsbrunner, H.; Harer, J., Stability of persistence diagrams, Discrete Comput. Geom., 37, 103-120, (2007) · Zbl 1117.54027
[15] Da, T.K.F., Yvinec, M.: 3D Alpha Shapes. In: cgal Editorial Board (ed.) 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
[16] Dey, T. K.; Wenger, R., Stability of critical points with interval persistence, Discrete Comput. Geom., 38, 479-512, (2007) · Zbl 1147.55006
[17] Dey, T. K.; Zhao, W., Approximate medial axis as a Voronoi subcomplex, Comput. Aided Des., 36, 195-202, (2004)
[18] Du, Q.; Faber, V.; Gunzburger, M., Centroidal Voronoi tessellations: Applications and algorithms, SIAM Rev., 41, 637-676, (1999) · Zbl 0983.65021
[19] Edelsbrunner, H.: Geometry and Topology for Mesh Generation. Cambridge University Press, New York (2001) · Zbl 0981.65028
[20] Edelsbrunner, H.; Facello, M. A.; Liang, J., On the definition and the construction of pockets in macromolecules, Discrete Appl. Math., 88, 83-102, (1998) · Zbl 0928.68113
[21] Edelsbrunner, H.; Letscher, D.; Zomorodian, A., Topological persistence and simplification, Discrete Comput. Geom., 28, 511-533, (2002) · Zbl 1011.68152
[22] Edelsbrunner, H.; Mücke, E. P., Three-dimensional alpha shapes, ACM Trans. Graph., 13, 43-72, (1994) · Zbl 0806.68107
[23] Freedman, D., Chen, C.: Measuring and localing homology classes. The Computing Research Repository (CoRR) (2007). http://arxiv.org/abs/0705.3061
[24] Giesen, J., Ramos, E.A., Sadri, B.: Medial axis approximation and unstable flow complex. In: Proceedings of the Symposium on Computational Geometry, pp. 327-336 (2006) · Zbl 1153.65321
[25] Leach, A.: Molecular Modelling: Principles and Applications. Prentice Hall, New York (2001)
[26] Lieutier, A., Any open bounded subset of ℝ \(n\) has the same homotopy type as its medial axis, Comput. Aided Des., 36, 1029-1046, (2004)
[27] Lun Cheng, H.; Dey, T. K.; Edelsbrunner, H.; Sullivan, J. M., Dynamic skin triangulation, Discrete Comput. Geom., 25, 2001, (2001) · Zbl 0984.68172
[28] Munkres, J.: Elements of Algebraic Topology. Addison-Wesley, Reading (1984) · Zbl 0673.55001
[29] Weisstein, E.W.: Spherical code, from mathworld—a wolfram web resource. http://mathworld.wolfram.com/sphericalcode.html (2000)
[30] Yaffe, E.: Efficient construction of pathways in the complement of the union of balls in ℝ3. M.Sc. Tel-Aviv University, September 2007. http://www.cs.tau.ac.il/eitanyaf/thesis.pdf
[31] Yaffe, E.; Fishelovitch, D.; Wolfson, H. J.; Halperin, D.; Nussinov, R., MolAxis: A server for identification of channels in macromolecule, Nucleic Acids Res., 36, w210-w215, (2008)
[32] Yaffe, E.; Fishelovitch, D.; Wolfson, H. J.; Halperin, D.; Nussinov, R., MolAxis: Efficient and accurate identification of channels in macromolecules, Proteins: Struct. Funct. Bioinform., 73.1, 72-86, (2008)
[33] Yaffe, E., Halperin, D.: Approximating the pathway axis and the persistence diagram of a collection of balls in 3-space. In: Proceedings of the Symposium on Computational Geometry, pp. 260-269 (2008) · Zbl 1271.68236
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.