![]() |
|
||||||||||||||||
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 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
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 sufficiently 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
The following figures
illustrate the definition of the graph induced complex. |
![]() |
![]() |
![]() |
Let (P,d) be a point set with a metric d and G(P) be a graph on P. | Let Q be a subset of P. Each point in P is mapped to its closest point in Q which is illustrated by the Voronoi diagram of Q. | The graph induced complex is constructed by collecting all simplices {q1, q2, ..., qk+1} if there is a (k+1)-clique in the graph G(P) with vertices {p1, p2, ..., pk+1} such that pi has qi (i=1,...,k+1) as its closest point in Q. |
![]() |
![]() |
|
This figure compares the ability of the simplicial complex to capture the H1. |
This figure compares the size of the simplicial complex. |
Surface
reconstruction by graph induced complex
![]() |
![]() |
Reconstructed meshes by using graph induced complex |