Graph Induced Complex on Point Data
Home

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 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 complex

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.

# 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]).

 Reconstructed meshes by using graph induced complex