Publication:2354923

DOI10.1145/2462356.2462387zbMath1329.62295arXiv1304.0662OpenAlexW2207207554MaRDI QIDQ2354923

Yusu Wang, Fengtao Fan, Tamal Krishna Dey

Publication date: 27 July 2015

Published in: Computational Geometry, Proceedings of the twenty-ninth annual symposium on Computational geometry (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/1304.0662

zbMATH Keywords

homologysimplicial complexsurface reconstructiontopological data analysissparsificationtopological persistencepoint cloud datagraph-induced complex

Mathematics Subject Classification ID

Image analysis in multivariate analysis (62H35) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computer-aided design (modeling of curves and surfaces) (65D17) Simplicial sets and complexes in algebraic topology (55U10) Other homology theories in algebraic topology (55N35)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The Simplex Tree: An Efficient Data Structure for General Simplicial Complexes
• Scalar field analysis over point cloud data
• Stability of persistence diagrams
• Clustering to minimize the maximum intercluster distance
• Reeb graphs: approximation and persistence
• Linear-size approximations to the Vietoris-Rips filtration
• Geodesic delaunay triangulations in bounded planar domains
• Approximating cycles in a shortest basis of the first homology group from point data
• On the Nonlinear Statistics of Range Image Patches
• The “λ-medial axis”
• Towards persistence-based reconstruction in euclidean spaces
• Computing Topological Persistence for Simplicial Maps
• A SIMPLE ALGORITHM FOR HOMEOMORPHIC SURFACE RECONSTRUCTION
• Vietoris-rips complexes also provide topologically correct reconstructions of sampled shapes
• Barcodes: The persistent topology of data
• Manifold reconstruction in arbitrary dimensions using witness complexes

Related Items (12)

Structure and stability of the one-dimensional Mapper ⋮ A higher-dimensional homologically persistent skeleton ⋮ The Offset Filtration of Convex Objects ⋮ Zigzag zoology: Rips zigzags for homology inference ⋮ Stabilizing the unstable output of persistent homology computations ⋮ The inverse Voronoi problem in graphs. I: Hardness ⋮ An approximate nerve theorem ⋮ Conley Index Approach to Sampled Dynamics ⋮ Anisotropic Triangulations via Discrete Riemannian Voronoi Diagrams ⋮ A comparison framework for interleaved persistence modules ⋮ Gromov-Hausdorff approximation of filamentary structures using Reeb-type graphs ⋮ Approximating persistent homology in Euclidean space through collapses

Uses Software

• ShortLoop

This page was built for publication: Graph induced complex on point data