Manifold Homotopy via the Flow Complex



Bardia Sadri

It is known that the critical points of the distance function induced by a dense sample P of a submanifold S of R
n are distributed into two groups, one lying close to S itself, called the shallow, and the other close to medial axis of S, 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 S itself and the union of the stable manifolds of the deep critical points have the homotopy type of the complement of S. 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 Rn, 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 the manifold reconstruction problem when the target dimension is unknown.

Symposium on Geometry Processing (SGP), special issue of Computer Graphics Forum, 28(5), 2009 [PDF]
Short version in proceedings of EuroCG’08 [PDF]
EuroCG Presentation Slides [PDF]
Slides from an invited talk in the SIAM Conference on Discrete Mathematics ’08 [PDF]