| We developed a new simplicial
complex called graph induced complex
for topological inference and surface reconstruction from point data.
It enjoys the the
of both Vietoris-Rips
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
induced complex one
(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.
H1 inference from a very sparse subsample
Using the concept of homological loop feature size (see [DFW13]), the graph induced complex can be very small but still capture the H1. In the Klein bottle example, there are 40,000 points sampled in R4. But the graph induced complex with size of 152 can still capture the H1 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].
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]).