


People Research Publications 
We developed a new simplicial
complex called graph induced complex
for topological inference and surface reconstruction from point data.
It enjoys the the
advantages
of both VietorisRips
and witness complexes. It
only needs a graph connecting the original sample points from which it
builds a complex on
the subsample thus taming the size considerably. We show that, using
the graph
induced complex one
can (i) infer the one dimensional homology of a manifold from a very lean subsample, (ii) reconstruct a surface in three dimension from a sparse subsample without computing Delaunay triangulations, (iii) infer the persistent homology groups of compact sets from a sufﬁciently dense sample. These results were published in the following paper: [DFW13] T. K. Dey, F. Fan, and Y. Wang. Graph Induced Complex on Point Data. Proc. 29th Annu. Sympos. Comput. Geom. (2013). GIComplex software based on the [DFW13] is available. This project is supported by NSF grants CCF 1318595, CCF 1319406, CCF 1116258 Construction of the graph induced complexThe following figures illustrate the definition of the graph induced complex.
H_{1} inference from a very sparse subsampleUsing the concept of homological loop feature size (see [DFW13]), the graph induced complex can be very small but still capture the H_{1}. In the Klein bottle example, there are 40,000 points sampled in R^{4}. But the graph induced complex with size of 152 can still capture the H_{1} of the Klein bottle. The following two figures give the comparison results between graph induced complex and another two popular simplicial complexes: Rips and witness complexes for this example. The descriptions of these figures are referred to the paper [DFW13].
Surface
reconstruction by graph induced complex Using graph induced complex, a sparse triangular mesh can be reconstructed from a very dense input point set sampled from a surface in 3D. The following two examples both have dense input point sets P with P > 1,000,000. The reconstructed meshes have size in thousands (see the size information in the paper [DFW13]).
