Weak feature size and persistent homology: computing homology of solids in Rn from noisy data samples

ABSTRACT

In this work, one proves that under quite general assumptions one can deduce the topology of a bounded open set in Rⁿ from a Hausdorff distance approximation of it. For this, one introduces the weak feature size (wfs) that generalizes the notion of local feature size. Our results apply to open sets with positive wfs, which include many sets whose boundaries are not smooth and even nowhere smooth. This class includes also the piecewise analytic open sets which cover many cases encountered in practical applications. The proofs are based on the study of distance functions to closed sets and their critical points. As an application, one gives an algorithmic way, thanks to persistent homology techniques, to compute the homology groups of open sets from noisy samples of points on their boundary.

REFERENCES

• 1: N. Amenta, S. Choi, T. Dey and N. Leekha A simple algorithm for homeomorphic Surface Reconstruction. International Journal of Computational Geometry and Applications Vol.12, No. 1,2(2002) pp.125--141.
• 2: N. Amenta and M. Bern Surface Reconstruction by Voronoi Filtering Discrete and Computational Geometry, no 22 pp.481--504(1999)
• 3: Jean-Daniel Boissonnat , Frédéric Cazals, Smooth surface reconstruction via natural neighbour interpolation of distance functions, Proceedings of the sixteenth annual symposium on Computational geometry, p.223-232, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong [doi>10.1145/336154.336208]
• 4: F. Chazal, A. Lieutier, Stability and homotopy of a subset of the medial axis (extended abstract), proc. ACM Symp. Solid Modeling and Applications , pp. 243--248 (2004).
• 5: F. Chazal, A. Lieutier, The λ-medial axis to appear in Graphical Models (GMOD), research report version available at http://math.ubourgogne.fr/topo/chazal/publications.htm.
• 6: F. Chazal, A. Lieutier, Weak feature size and persistent homology: computing homology of solids in Rn from noisy data samples, research report available at http://math.u-bourgogne.fr/topo/chazal/publications.htm
• 7: F. Chazal , R. Soufflet, Stability and Finiteness Properties of Medial Axis and Skeleton, Journal of Dynamical and Control Systems, v.10 n.2, p.149-170, April 2004 [doi>10.1023/B:JODS.0000024119.38784.ff]
• 8: J. Cheeger, Critical Points of Distance Functions and Applications to Geometry, Geometric Topology: recent developments, Montecatini Terme, 1990, Springer Lecture Notes, 1504 (1991), 1--38.
• 9: F. H. Clarke, Optimization and Non Smooth Analysis, Wiley-Interscience, New-York, 1983.
• 10: F. H. Clarke, Generalized gradients and applications, Trans. Amer. Math. Soc. 205 (1975), 247--262.
• 11: 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]
• 12: Tamal K. Dey , Samrat Goswami, Provable surface reconstruction from noisy samples, Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA [doi>10.1145/997817.997867]
• 13: H. Edelsbrunner. Surface reconstruction by wrapping finite point sets in space, in Ricky Pollack and Eli Goodman Festschrift ed. B. Aronov, S. Basu, J. Pach and M. Sharir.Springer-Verlag, 379--404
• 14: H. Edelsbrunner, D. Letscher, A. Zomorodian, Topological Persistence and Simplifications, Discrete Comput. Geom. 28 (2002) pp. 511--533.
• 15: 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]
• 16: J.H.G. Fu, Tubular Neighborhoods in Euclidean Spaces, Duke Math. Jornal, Vol. 52, No. 4 (1995).
• 17: K. Grove, Critical Point Theory for Distance Functions, Proc. of Symposia in Pure Mathematics, Vol. 54 (1993), Part 3.
• 18: K. Grove, K. Shiohama, A generalized sphere theorem, Ann. of Math., vol 106, 1977, pp 201--211.
• 19: A. Lieutier, Any open bounded subset of Rn has the same homotopy type as its medial axis, Computer-Aided Design, 36(2004) 1029--1046, Elsevier.
• 20: J. R. Munkres. Elements of Algebraic Topology. Addison-Wesley Publishing Company, 1984.
• 21: P. Niyogi, S. Smale, S. Weinberger, Finding the Homology of Submanifolds with High Confidence from Random Samples, preprint, Sept. 2004, available at http://www.tti-c.org/smale_papers.html
• 22: E. H. Spanier. Algebraic Topology Mc Graw-Hill Series in Higher Mathematics, 1966.
• 23: Afra Joze Zomorodian , Herbert Edelsbrunner, Computing and comprehending topology: persistence and hierarchical morse complexes, 2001

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.0 GENERAL

Additional Classification:
  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING

General Terms:
Algorithms, Measurement, Theory

Keywords:
homotopy type, reverse engineering, surface reconstruction, topological persistence