Frédéric Chazal
ABSTRACT
Given a smooth compact codimension one submanifold S of Rk 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 Rk\K is homotopy equivalent to the medial axis of S. We obtain similar results for smooth compact submanifolds S of Rk of any codimension.
- N. Amenta and M. Bern Surface Reconstruction by Voronoi Filtering Discrete and Computational Geometry, no 22 pp. 481--504 (1999). Google Scholar
Digital Library
- 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.Google ScholarCross Ref
- N. Amenta, T.J. Peters, A. Russell, Computational Topology: Ambient Isotopic Approximation of 2-Manifolds, in Theoretical Computer Science 305, 3--15, 2003. Google ScholarDigital Library
- F. Chazal, D. Cohen-Steiner, A. Lieutier A sampling theory for compacts in Euclidean space, submitted.Google Scholar
- F. Chazal, A. Lieutier, The λ-medial axis, Graphical Models, Volume 67, 4 (2005), Pages 304--331. Google ScholarDigital Library
- F. Chazal, A. Lieutier, Weak feature size and persistent homology: computing homology of solids in Rn from noisy data samples, in ACM Symp. of Computational Geometry 2005. Google ScholarDigital Library
- 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.htmGoogle Scholar
- 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.Google Scholar
- F.H. Clarke, Optimization and NonSmooth Analysis, Wiley-Interscience, New-York, 1983.Google Scholar
- T. K. Dey and S. Goswami, Provable surface reconstruction from noisy samples, Proc. 20th Annu. Sympos. Comput. Geom. (2004), 330--339. Google ScholarDigital Library
- T.K. Dey, J. Giesen, E. Ramos and B. Sadri, Critical Points of the Distance to an epsilon-Sampling on a Surface and Flow Based Surface Reconstruction. ACM Symposium on Comp. Geometry, (2005). Google ScholarDigital Library
- T. K. Dey and S. Goswami, Tight cocone: A watertight surface reconstruction. J. Computing Informat. Sci. Engin. 12 (2003), 302--307.Google ScholarCross Ref
- S.-W. Cheng, T.K. Dey, and E.A. Ramos, Manifold Reconstruction from Point Samples. Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, 2005, pp. 1018-1027. Google ScholarDigital Library
- H. Edelsbrunner, E. P. Mucke. Three-dimensional alpha shapes, ACM Trans. Graphics 13 (1994), 43--72. Google ScholarDigital Library
- H. Federer, Geometric measure theory, Springer Verlag (1969).Google Scholar
- K. Grove, Critical Point Theory for Distance Functions, Proc. of Symposia in Pure Mathematics, Vol. 54 (1993), Part 3.Google Scholar
- A. Lieutier, Any open bounded subset of Rn has the same homotopy type as its medial axis, Journal of Computer-Aided Design, 2004.Google Scholar
- 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. Google ScholarDigital Library
- 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.htmlGoogle Scholar
Index Terms
- Topology guaranteeing manifold reconstruction using distance function to noisy data
Recommendations
Smooth manifold reconstruction from noisy and non-uniform approximation with guarantees
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 ...
Implicit Manifold Reconstruction
AbstractLet $${{\mathcal {M}}} \subset \mathbb {R}^d$$ be a compact, smooth and boundaryless manifold with dimension m and unit reach. We show how to construct a function $$\varphi :\mathbb {R}^d \rightarrow \mathbb {R}^{d-m}$$ from a uniform $$(\...
A Sampling Theory for Compact Sets in Euclidean Space
We introduce a parameterized notion of feature size that interpolates between the minimum of the local feature size and the recently introduced weak feature size. Based on this notion of feature size, we propose sampling conditions that apply to noisy ...
Comments