Topology guaranteeing manifold reconstruction using distance function to noisy data

ABSTRACT

Given a smooth compact codimension one submanifold S of R^k and a compact approximation K of S, we prove that it is possible to reconstruct S and to approximate the medial axis of S with topological guarantees using unions of balls centered on K. We consider two notions of noisy-approximation that generalize sampling conditions introduced by Amenta & al. and Dey & al. Our results are based upon critical point theory for distance functions. For the two approximation conditions, we prove that the connected components of the boundary of unions of balls centered on K are isotopic to S. Our results allow to consider balls of different radii. For the first approximation condition, we also prove that a subset (known as the λ medial axis) of the medial axis of R^k\K is homotopy equivalent to the medial axis of S. We obtain similar results for smooth compact submanifolds S of R^k of any codimension.

REFERENCES

• 1: Nina Amenta , Marshall Bern, Surface reconstruction by Voronoi filtering, Proceedings of the fourteenth annual symposium on Computational geometry, p.39-48, June 07-10, 1998, Minneapolis, Minnesota, United States [doi>10.1145/276884.276889]
• 2: N. Amenta, S. Choi, T. Dey and N. Leekha, A Simple Algorithm for Homeomorphic Surface Reconstruction, in Int. Journal of Computational Geometry and its Applications vol. 12, (2002), 125--141.
• 3: Nina Amenta , Thomas J. Peters , Alexander C. Russell, Computational topology: ambient isotopic approximation of 2-manifolds, Theoretical Computer Science, v.305 n.1-3, p.3-15, 18 August 2003 [doi>10.1016/S0304-3975(02)00691-6]
• 4: F. Chazal, D. Cohen-Steiner, A. Lieutier A sampling theory for compacts in Euclidean space, submitted.
• 5: 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]
• 6: 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]
• 7: F. Chazal, A. Lieutier, Topology guaranteeing manifold reconstruction using distance function to noisy data, Research Report 429 (2005), available at http://math.u-bourgogne.fr/topo/chazal/publications.htm
• 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 NonSmooth Analysis, Wiley-Interscience, New-York, 1983.
• 10: 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]
• 11: Tamal K. Dey , Joachim Giesen , Edgar A. Ramos , Bardia Sadri, Critical points of the distance to an epsilon-sampling of a surface and flow-complex-based surface reconstruction, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy [doi>10.1145/1064092.1064126]
• 12: T. K. Dey and S. Goswami, Tight cocone: A watertight surface reconstruction. J. Computing Informat. Sci. Engin. 12 (2003), 302--307.
• 13: Siu-Wing Cheng , Tamal K. Dey , Edgar A. Ramos, Manifold reconstruction from point samples, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 14: 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]
• 15: H. Federer, Geometric measure theory, Springer Verlag (1969).
• 16: K. Grove, Critical Point Theory for Distance Functions, Proc. of Symposia in Pure Mathematics, Vol. 54 (1993), Part 3.
• 17: A. Lieutier, Any open bounded subset of Rn has the same homotopy type as its medial axis, Journal of Computer-Aided Design, 2004.
• 18: B. Mederos, N. Amenta, L. Vehlo and L. H. de Figueiredo, Surface reconstruction from noisy point clouds, Eurographics Symposium on Geometry Processing, 2005, pages 53--62.
• 19: 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

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling

General Terms:
Algorithms, Theory

Keywords:
distance function, sampling, surface and manifold reconstruction