Efficient Computation of Topological Features from Point Data and Shapes
The topological features of an object are features which are preserved while continuously deforming the object. Examples are the dimension of an object and the number of holes in it. In contrast, the geometric features of an object such as its volume can dramatically change under such deformations. The robustness of topological features makes them more appealing for analyzing objects in the presence of noise, which is inevitable in practice. Researchers in various areas such as topological data analysis, computer graphics, visualization, and sensor networks have shown an increased need for efficient algorithms for computing topological features. Such demands inspire my PhD research work.
In this talk, I will present two results of mine on efficient computation of topological features. The first result is about a new simplicial complex called graph induced complex. Nowadays, point data are often sampled from hidden objects in a large size such that the topological inference on such dense points becomes computationally prohibitive. The graph induced complex is designed to cope with such difficulty. It works on subsamples as is done in the case of witness complexes and thus generally is small in size. At the same time, unlike the witness complex, it still carries significant topological information of the underlying space as the Rips complex does. It is proved that the graph induced complex can be used not only for topological inference of manifolds and compact sets in arbitrary Euclidean space but also for the reconstruction of surfaces in 3D.
The second result I will present is an efficient algorithm for computing the so called handle and tunnel loops of closed surfaces in 3D which resemble intuitive handles and tunnels. The handle and tunnel loops have a variety of applications in computer graphics and shape analysis. There are two provable algorithms for computing them, both of which suffer from the limitation that some explicit structures of the interior and exterior bounded by the closed surface are required. Computing these additional structures is often very costly. Our new algorithm eliminates this limitation by leveraging the properties of the Reeb graph. Experiments show that our method is significantly faster than previous ones.
All these two results are joint work with Tamal Dey and Yusu Wang.