2013/04/02 by Tamal K. Dey, Fengtao Fan, Dey, Tamal K. +3
Computer Science · Mathematics · #Algebraic Topology (math.AT) #Computational Geometry (cs.CG) #Digital Image Processing Techniques #FOS: Computer and information sciences #FOS: Mathematics #Topological and Geometric Data Analysis #cs.CG #math.AT
paper · pdf · doi:10.48550/arxiv.1304.0662
29th Annual Symposium on Computational Geometry, 2013 (to appear)
arxiv created 2013/04/02 · openalex publication_date 2013/04/02 · arxiv updated 2013/04/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The efficiency of extracting topological information from point data depends largely on the complex that is built on top of the data points. From a computational viewpoint, the most favored complexes for this purpose have so far been Vietoris-Rips and witness complexes. While the Vietoris-Rips complex is simple to compute and is a good vehicle for extracting topology of sampled spaces, its size is huge--particularly in high dimensions. The witness complex on the other hand enjoys a smaller size because of a subsampling, but fails to capture the topology in high dimensions unless imposed with extra structures. We investigate a complex called the \em graph induced complex that, to some extent, enjoys the advantages of both. It works on a subsample but still retains the power of capturing the topology as the Vietoris-Rips complex. 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. We provide experimental evidences in support of our theory.