Cited By
View all- Sheehy DCzumaj A(2018)Fréchet-stable signatures using persistence homologyProceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3174304.3175341(1100-1108)Online publication date: 7-Jan-2018
Manifold homotopy via the flow complex
Pages 1361 - 1370
Abstract
It is known that the critical points of the distance function induced by a dense sample P of a submanifold Σ of ℝn are distributed into two groups, one lying close to Σ itself, called the shallow, and the other close to medial axis of Σ, called deep critical points. We prove that under (uniform) sampling assumption, the union of stable manifolds of the shallow critical points have the same homotopy type as Σ itself and the union of the stable manifolds of the deep critical points have the homotopy type of the complement of Σ. The separation of critical points under uniform sampling entails a separation in terms of distance of critical points to the sample. This means that if a given sample is dense enough with respect to two or more submanifolds of ℝn, the homotopy types of all such submanifolds together with those of their complements are captured as unions of stable manifolds of shallow versus those of deep critical points, in a filtration of the flow complex based on the distance of critical points to the sample. This results in an algorithm for homotopic manifold reconstruction when the target dimension is unknown.
References
[1]
{AB99} Nina Amenta and Marshall W. Bern. Surface reconstruction by Voronoi filtering. Discrete Comput. Geom., 22:481--504, 1999.
[2]
{ABCO+01} Marc Alexa, Johannes Behr, Daniel Cohen-Or, Shachar Fleishman, David Levin, and Cláudio T. Silva. Point set surfaces. In IEEE Visualization, 2001.
[3]
{ABE98} Nina Amenta, Marshall W. Bern, and David Eppstein. The crust and the β-skeleton: Combinatorial curve reconstruction. Graphical Models and Processing, 60(2):125--135, 1998.
[4]
{ACDL02} Nina Amenta, Sunghee Choi, Tamal K. Dey, and N. Leekha. A simple algorithm for homeomorphic surface reconstruction. Internat. J. Comput. Geom. Appl., 12(1--2):125--141, 2002.
[5]
{ACK01} Nina Amenta, Sunghee Choi, and Ravi Krishna Kolluri. The power crust, unions of balls, and the medial axis transform. Comput. Geom. Theory Appl., 19(2--3):127--153, 2001.
[6]
{APR03} Nina Amenta, Thomas J. Peters, and Alexander Russell. Computational topology: Ambient isotopic approximation of 2-manifolds. Theo. Comp. Sci., 305(1--3):3--15, 2003.
[7]
{BC02} Jean-Daniel Boissonnat and Frédéric Cazals. Smooth surface reconstruction via natural neighbour interpolation of distance functions. Comput. Geom. Theory Appl., 22(1--3):185--203, 2002.
[8]
{BDGa08} Kevin Buchin, Tamal K. Dey, Joachim Giesen, and Matthias John and. Recursive geometry of the flow complex and topology of the flow complex filtration. Comput. Geom. Theory Appl., 40:115--157, 2008.
[9]
{BG05} Kevin Buchin and Joachim Giesen. Flow complex: General structure and algorithms. In Proc. 16th Canad. Conf. Comput. Geom., pages 270--273, 2005.
[10]
{BO06} Jean-Daniel Boissonnat and Steve Oudot. Provably good sampling and meshing of Lipschitz surfaces. In Proc. 22nd Annu. ACM Sympos. Comput. Geom., pages 337--346, 2006.
[11]
{Boi84} Jean-Daniel Boissonnat. Geometric structures for three-dimensional shape representation. ACM Trans. Graph., 3(4):266--286, 1984.
[12]
{Caz06} Frédéric Cazals. Robust construction of the extended three-dimensional flow complex. Research Report 5903, INRIA, 2006.
[13]
{CCSL06} Frédéric Chazal, David Cohen-Steiner, and André Lieutier. A sampling theory for compacts in Euclidean space. In Proc. 22nd Annu. ACM Sympos. Comput. Geom., pages 319--326, 2006.
[14]
{CG06} Frédéric Cazals and Joachim Giesen. Delaunay triangulation based surface reconstruction. In Jean-Daniel Boissonnat and Monique Teillaud, editors, Effective Computational Geometry for Curves and Surfaces. Springer-Verlag, 2006.
[15]
{CL06} Frédéric Chazal and André Lieutier. Topology guaranteeing manifold reconstruction using distance function to noisy data. In Proc. 22nd Annu. ACM Sympos. Comput. Geom., pages 112--118, 2006.
[16]
{CO08} Frédéric Chazal and Steve Yann Oudot. Towards persistence-based reconstruction in euclidean spaces. In SCG '08: Proceedings of the twenty-fourth annual symposium on Computational geometry, pages 232--241, 2008.
[17]
{DGJ03} Tamal K. Dey, Joachim Giesen, and Matthias John. Alpha-shapes and flow shapes are homotopy equivalent. In Proc. 35th Annu. ACM Sympos. Theory Comput., pages 493--502, 2003.
[18]
{DGRS05} Tamal K. Dey, Joachim Giesen, Edgar A. Ramos, and Bardia Sadri. Critical points of the distance to an epsilon-sampling of a surface and flow-complex-based surface reconstruction. In Proc. 21st Annu. ACM Sympos. Comput. Geom., pages 218--227, 2005.
[19]
{Ede95} H. Edelsbrunner. The union of balls and its dual shape. Discrete Comput. Geom., 13:415--440, 1995.
[20]
{Ede04} Herbert Edelsbrunner. Surface reconstruction by wrapping finite point sets in space. Discrete & Computational Geometry, 32:231--244, 2004.
[21]
{GJ02} Joachim Giesen and Matthias John. Surface reconstruction based on a dynamical system. Computer Graphics Forume, 21:363--371, 2002.
[22]
{GJ03} Joachim Giesen and Matthias John. The flow complex: A data structure for geometric modeling. In Proc. 14th ACM-SIAM Sympos. Discrete Algorithms, pages 285--294, 2003.
[23]
{GO07} Leonidas J. Guibas and Steve Oudot. Reconstruction using witness complexes. In Proc. 18th ACM-SIAM Sympos. Discrete Algorithms, pages 1076--1085, 2007.
[24]
{Gro93} Karl Grove. Critical point theory for distance functions. Symposia in Pure Mathematics, 54(3):357--385, 1993.
[25]
{GRS06} Joachim Giesen, Edgar A. Ramos, and Bardia Sadri. Medial axis approximation and unstable flow complex. In Proc. 22nd Annu. ACM Sympos. Comput. Geom. pages 327--336, 2006.
[26]
{Hat01} Allen Hatcher. Algebraic Topology. Cambridge University Press, 2001.
[27]
{HDD+92} Hugues Hoppe, Tony DeRose, Tom Duchamp, John Alan McDonald, and Werner Stuetzle. Surface reconstruction from unorganized points. In Proc. SIGGRAPH '92, pages 71--78, 1992.
[28]
{Lie04} André Lieutier. Any bounded open subset of ℝ n has the same homotopy type as its medial axis. Computer-Aided Design, 36(11):1029--1046, 2004.
[29]
{NSW06} P. Niyogi, S. Smale, and S. Weinberger. Finding the homology of submanifolds with high confidence from random samples. Discrete & Computational Geometry, 2006.
[30]
{Pet07} A. Petrunin. Semiconcave functions in alexandrov geometry. In Surveys in Differential Geometry, volume XI: Metric and Comparison Geometry. International Press of Boston, 2007.
[31]
{Sad06} Bardia Sadri. Surface and Medial Axis Topology Through Distance Flows Induced by Discrete Samples. PhD thesis, University of Illinois at Urbana-Champaign, 2006.
[32]
{Sie99} Dirk Siersma. Voronoi diagrams and morse theory of the distance function. In O. E. Barndorff-Nielsen and E. B. V. Jensen, editors, Geometry in Present Day Science, pages 187--208. World Scientific, 1999.
Index Terms
- Manifold homotopy via the flow complex
Recommendations
Riemannian Manifold Learning
Recently, manifold learning has been widely exploited in pattern recognition, data analysis, and machine learning. This paper presents a novel framework, called Riemannian manifold learning (RML), based on the assumption that the input high-dimensional ...
Incremental manifold learning via tangent space alignment
ANNPR'06: Proceedings of the Second international conference on Artificial Neural Networks in Pattern RecognitionSeveral algorithms have been proposed to analysis the structure of high-dimensional data based on the notion of manifold learning. They have been used to extract the intrinsic characteristic of different type of high-dimensional data by performing ...
Stable Embedding of Grassmann Manifold via Gaussian Random Matrices
Compressive sensing (CS) provides a new perspective for data reduction without compromising performance when the signal of interest is sparse or has intrinsically low-dimensional structure. The theoretical foundation for most of the existing studies on CS ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Publisher
Eurographics Association
Goslar, Germany
Publication History
Published: 15 July 2009
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 5Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 24 Jan 2025
Other Metrics
Citations
Cited By
View all- Sheehy DCzumaj A(2018)Fréchet-stable signatures using persistence homologyProceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3174304.3175341(1100-1108)Online publication date: 7-Jan-2018